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). |
Contents
Introduction | 1 |
Morphisms in logic and complexity | 16 |
A stronger process of branching | 24 |
4 | 31 |
Geometric aspects of cut elimination | 109 |
Feasibility graphs | 155 |
Bounds for finite visibilities | 180 |
Some related computational questions | 212 |
Stronger forms of recursion | 355 |
Groups and graphs | 404 |
10 | 410 |
DECE | 424 |
19 | 432 |
Extended notions of automata | 436 |
22 | 446 |
Geometry of scales in metric spaces | 449 |
Mappings and graphs | 231 |
Mappings and comparisons | 285 |
Adjacency matrices and counting | 294 |
Duality and NPcompleteness | 313 |
Finite automata and regular languages | 327 |
Constructions with graphs | 338 |
The Corona decomposition revisited | 465 |
Appendix | 480 |
487 | |
496 | |
497 | |
Common terms and phrases
atomic occurrences automatic structure automaton basepoint basic bilipschitz binary Boolean Boolean circuits bounded Cayley graph chain of focal computations 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 group focal pairs focusing branch points follows formal proofs formulae G and H G which begins geometry given graph G Heisenberg group implicit implies incoming edges injection input vertices Lemma length Let G local isomorphism logical flow graph loops metric space minimal folding graph minimal representation nontrivial oriented cycles normalized value function NP-complete number of edges number of vertices optical graph orientation-preserving mapping oriented graph oriented path output vertex path in G polynomial Proposition represent rooted trees Section sequent set of vertices subgraph surjection total number unary operations vertex vertices in G visibility graphs weak mapping word metric
References to this book
Interactive Systems: Design, Specification, and Verification: 8th ... Chris J. Johnson No preview available - 2001 |