Structure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986 (Lecture Notes in Computer Science, 223, Band 223) - Softcover

Selman, Alan L.

 
9783540164869: Structure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986 (Lecture Notes in Computer Science, 223, Band 223)
Softcover
ISBN 10: 3540164863 ISBN 13: 9783540164869
Verlag: Springer, 2008

Inhaltsangabe

The complexity of sparse sets in P.- Isomorphisms and 1-L reductions.- Randomness, relativizations, and polynomial reducibilities.- On non-uniform polynomial space.- One-way functions and circuit complexity.- Relativized alternation.- The polynomial hierarchy and intuitionistic Bounded Arithmetic.- With probability one, a random oracle separates PSPACE from the polynomial-time hierarchy.- The boolean hierarchy: Hardware over NP.- Exponential time and bounded arithmetic.- Probabilistic game automata.- Two lower bound arguments with "inaccessible" numbers.- Resource-bounded Kolmogorov complexity of hard languages.- A note on one-way functions and polynomial time isomorphisms.- What is a hard instance of a computational problem?.- The complexity of optimization problems.- The power of the queue.- A depth-size tradeoff for boolean circuits with unbounded fan-in.- An optimal lower bound for turing machines with one work tape and a two-way input tape.- Separation results for bounded alternation.- Parallel computation with threshold functions.- The topology of provability in complexity theory.- Optimal approximations of complete sets.- Expanders, randomness, or time versus space.- Diagonalisation methods in a polynomial setting.- Bounded oracles and complexity classes inside linear space.- Parallel computation and the NC hierarchy relativized.- Probabilistic quantifiers, adversaries, and complexity classes : An overview.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.

Verlag
Springer
Erscheinungsdatum
2008
Sprache
Englisch
ISBN 10 
3540164863
ISBN 13 
9783540164869
Einband
Taschenbuch
Anzahl der Seiten
412
Kontakt zum Hersteller
Nicht verfügbar
Verantwortliche Person
Springer Nature Customer Service Center GmbH
ProductSafety@springernature.com

Europaplatz 3
Heidelberg
69115
Deutschland

Weitere beliebte Ausgaben desselben Titels

9780387164861: Structure in Complexity Theory (Lecture Notes in Computer Science)

Vorgestellte Ausgabe

ISBN 10:  0387164863 ISBN 13:  9780387164861
Verlag: Springer Verlag, 1986
Softcover