Verkauf durch Sack Fachmedien

Selman

Structure in Complexity Theory

Medium: Buch
ISBN: 978-3-540-16486-9
Verlag: Springer
Erscheinungstermin: 01.05.1986
Lieferfrist: bis zu 10 Tage

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.


Produkteigenschaften


  • Artikelnummer: 9783540164869
  • Medium: Buch
  • ISBN: 978-3-540-16486-9
  • Verlag: Springer
  • Erscheinungstermin: 01.05.1986
  • Sprache(n): Englisch
  • Auflage: 1986
  • Serie: Lecture Notes in Computer Science
  • Produktform: Kartoniert, Paperback
  • Gewicht: 1270 g
  • Seiten: 404
  • Format (B x H x T): 155 x 235 x 23 mm
  • Ausgabetyp: Kein, Unbekannt
Autoren/Hrsg.

Herausgeber

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.