A Graphic Apology for Symmetry and Implicitness

Front Cover
Oxford University Press, 2000 - Computers - 501 pages
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).
 

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
References
487
Index
496
28
497
Copyright

Common terms and phrases

About the author (2000)

A. Carbone, Associate Professor of Computer Science, University of Paris XII, France S. Semmes, Professor of Mathematics, Rice University, Houston, USA