A Graphic Apology for Symmetry and Implicitness

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

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

Common terms and phrases

References to this book

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

Bibliographic information