## A Graphic Apology for Symmetry and ImplicitnessThis book brings into focus the contrast between explicit and implicit algorithmic descriptions of objects and presents a new geometric language for the study of combinatorial and logical problems in complexity theory. These themes are considered in a variety of settings, sometimes crossing traditional boundaries. Special emphasis is given to moderate complexity - exponential or polynomial - but objects with multi-exponential complexity also fit in. Among the items under consideration are graphs, formal proofs, languages, automata, groups, circuits, some connections with geometry of metric spaces, and complexity classes (P, NP, co-NP). |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction | 1 |

Morphisms in logic and complexity | 15 |

Graphs and their visibilities | 37 |

Asymptotic growth of infinite visibilities | 88 |

Geometric aspects of cut elimination | 109 |

Feasibility graphs | 155 |

Bounds for finite visibilities | 180 |

Some related computational questions | 212 |

Finite automata and regular languages | 327 |

Constructions with graphs | 338 |

Stronger forms of recursion | 355 |

Groups and graphs | 404 |

Extended notions of automata | 436 |

Geometry of scales in metric spaces | 449 |

The Corona decomposition revisited | 465 |

Appendix | 480 |

Mappings and graphs | 231 |

Mappings and comparisons | 285 |

Adjacency matrices and counting | 294 |

Duality and NPcompleteness | 313 |

487 | |

496 | |

### Common terms and phrases

1O graphs atomic occurrences automaton basepoint basic bilipschitz binary Boolean circuits bounded Cayley graph chain of focal construction contains contractions Corollary corresponding cut elimination defined Definition denote edges in G endpoints endsequent equivalence class exactly example exponential feasibility graphs finite finitely-generated groups focal pairs focusing branch points follows formal proofs formulae G and H G which begins geometry given graph G Heisenberg group Hn(Z implicit implies incoming edges injection input vertices isomorphism Lemma length Let G logical flow graph loops metric space minimal folding graph minimal representation nontrivial oriented cycles normalized value function notion NP-complete number of edges number of vertices optical graph oriented graph oriented path output vertex path in G polynomial precise Proposition regular expressions regular languages represent rooted trees Section 4.3 sequent set of vertices subgraph subproofs subset surjection topological total number unary operations vertex vertices in G visibility graphs visibility V+(v,G weak mapping words