A Graphic Apology for Symmetry and Implicitness

by Carbone, Alessandra; Semmes, Stephen

• ISBN13: 9780198507291
• ISBN10: 0198507291
• Format: Hardcover
• Copyright: 2000-08-24
• Publisher: Oxford University Press

Summary

This 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).

Table of Contents

Introduction	1	(14)
Examples of implicit descriptions	1	(3)
Formal proofs and cut elimination	4	(1)
Feasibility	5	(1)
Combinatorial models	5	(3)
Formal proofs and algorithmic complexity	8	(1)
The role of symmetry	9	(1)
Partial symmetries	9	(1)
Computational complexity	10	(5)
Morphisms in logic and complexity	15	(4)
Morphisms and formal proofs	15	(1)
Morphisms and monotonicity	16	(1)
Combinatorial ``proof systems''	17	(2)
Exponential processes and formal proofs	19	(18)
Preliminaries	19	(3)
A process of branching	22	(2)
A stronger process of branching	24	(4)
Comparisons	28	(1)
The pigeon-hole principle	29	(1)
Proofs, sets, and cells	30	(7)
Graphs and their visibilities	37	(51)
Optical graphs	37	(1)
The definition of the ``visibility''	38	(1)
Some examples	39	(4)
Visibility and depth	43	(2)
The canonical projection	45	(1)
Basic properties of the visibility	46	(2)
The size of the visibility	48	(2)
Formal proofs and logical flow graphs	50	(3)
Comparison with L-systems	53	(3)
``Visibility'' in Riemannian manifolds	56	(9)
Universal covering spaces	65	(11)
Boolean circuits and expressions	76	(5)
Combinatorial dynamical systems	81	(3)
Exponential expansion	84	(4)
Asymptotic growth of infinite visibilities	88	(21)
Introduction	88	(1)
When loops meet	89	(2)
When loops do not meet	91	(13)
Summary and remarks	104	(1)
Asymptotic geometry	105	(4)
Geometric aspects of cut elimination	109	(46)
Preliminary remakrs	109	(2)
The process of cut elimination	111	(3)
A first scenario, and the breaking of cycles	114	(1)
A second scenario, and the breaking of focal pairs	115	(1)
A third scenario, and chains of focal pairs	115	(5)
The third scenario, continued	120	(1)
Chains of focal pairs in the second scenario	121	(1)
Recapitualtion	122	(2)
Proofs without focal pairs	124	(1)
A fourth scenario, and the creation of focal pairs	125	(1)
Extensions of chains of focal pairs	125	(1)
Steady graphs and cut-free proofs	126	(6)
Steady graphs with oriented cycles	132	(1)
Steady horizons	133	(3)
A simplified model	136	(3)
Comparisons	139	(1)
A brief digression	140	(3)
Proofs with simple cuts	143	(12)
Feasibility graphs	155	(25)
Basic concepts	155	(4)
Extensions and comparisons	159	(2)
Some remarks about computability	161	(1)
Feasibility and visibility graphs	162	(2)
Upper bounds	164	(1)
Concrete examples	165	(3)
Measurements of complexity in groups	168	(2)
Trivial words in groups	170	(5)
Examples about numbers	175	(1)
Trees	176	(1)
Boolean circuits	177	(1)
Homomorphisms and comparisons	178	(2)
Bounds for finite visibilities	180	(32)
The propagator rule	180	(3)
Visibilities within visibilities	183	(2)
The Calderon-Zygmund decomposition	185	(3)
The Corona decomposition	188	(3)
The derived graph	191	(1)
Extensions	192	(3)
A more direct counting argument	195	(5)
Exponential bounds for general graphs	200	(7)
The restrained visibility	207	(3)
Graphs with cycles	210	(2)
Some related computational questions	212	(19)
The size of the visibility	212	(4)
The visibility recognition problem	216	(4)
An implicit version	220	(1)
The visibility isomorphism problem	221	(7)
Computations with implicit descriptions	228	(3)
Mappings and graphs	231	(54)
Mappings and weak mappings	231	(4)
Computational questions	235	(1)
Local +-isomorphisms	236	(6)
Some interpretations	242	(1)
The local +-injection problem	243	(4)
A uniqueness result	247	(1)
Minimal representations	248	(4)
Mappings and effective witnesses	252	(1)
The visibility isomorphism problem	253	(4)
Minimal representations and DP	257	(1)
Minimal folding graphs	258	(4)
Universal constructions	262	(4)
The visibility spectrum	266	(5)
The local +-isomorphism problem	271	(4)
Comparisons with k-provability	275	(1)
A partial ordering between graphs	276	(2)
Monotonicity properties	278	(1)
Possible behavior of mappings	279	(3)
Possible behavior of mappings, continued	282	(3)
Mappings and comparisons	285	(9)
Locally +-stable mappings	285	(2)
Locally +-uniform mappings	287	(1)
Mappings and symmetry	288	(1)
Labelled graphs	289	(1)
Feasibility graphs	290	(4)
Adjacency matrices and counting	294	(19)
The adjacency matrix	294	(1)
Counting in the visibility	295	(4)
Some concrete examples	299	(11)
Representation problems	310	(1)
Mappings and matrices	311	(2)
Duality and NP-completeness	313	(14)
The visibility mapping problem	313	(4)
Monotonicity and stability properties	317	(2)
The visibility surjection problem	319	(5)
The visibility injection problem	324	(3)
Finite automata and regular languages	327	(11)
Definitions and the subset construction	327	(5)
Geometric reformulations	332	(2)
An extended view	334	(1)
Markov languages	335	(3)
Constructions with graphs	338	(17)
Mappings and automata	338	(1)
Cartesian products and concatenation	339	(3)
Free products and positive closure	342	(1)
Unions and intersections	343	(2)
Fiber products (in general)	345	(3)
Fiber products of graphs	348	(4)
Interpretations for automata	352	(3)
Stronger forms of recursion	355	(49)
Feasible numbers	356	(2)
Combinatorial interpretations	358	(3)
Feasibility graphs for feasibility graphs	361	(8)
Correspondence with functions	369	(3)
Implicit representations of functions	372	(1)
Functions and points	373	(2)
Graphs and numbers	375	(3)
Graphs and numbers, continued	378	(3)
Rings and semirings	381	(3)
Feasibility of sets	384	(5)
Visual interpretations	389	(1)
Codings and sets	390	(2)
Other operations	392	(3)
Simulations and conversions	395	(2)
Sums and visibility graphs	397	(2)
Back to formal proofs	399	(5)
Groups and graphs	404	(32)
Cayley graphs and the word metric	404	(2)
Pause for some definitions	406	(2)
The Heisenberg groups	408	(5)
Geometry of Heisenberg groups	413	(5)
Automatic groups	418	(2)
Automatic structures for graphs	420	(10)
Between Cayley graphs and graphs in general	430	(1)
Scales and paths	430	(1)
Connections between scales and paths	431	(3)
The k-fellow traveller property	434	(2)
Extended notions of automata	436	(13)
Asynchronous automata	437	(3)
Heisenberg groups	440	(1)
Expanding automata	441	(4)
Tapes that cross	445	(4)
Geometry of scales in metric spaces	449	(16)
Metric spaces and length spaces	449	(2)
Discretizations of metric spaces	451	(5)
The scale-geometry graph	456	(2)
Conditions of bounded geometry	458	(2)
Automatic structures	460	(1)
Making choices	461	(2)
A geometric caveat	463	(1)
The doubling condition	464	(1)
The Corona decomposition revisited	465	(22)
Interesting paths	465	(2)
Reduced graphs	467	(3)
Crisp paths	470	(3)
A weak mapping between visibilities	473	(3)
Injectivity properties of the weak mapping	476	(1)
Bounds	477	(3)
Appendix
A Formal proofs: A brief review	480	(7)
A.1 Sequent calculus	480	(3)
A.2 Cut elimination	483	(1)
A.3 The logical flow graph	484	(3)
References	487	(9)
Index	496