Structure in Complexity Theory Proceedings of the Conference held at the University of California, Berkeley, California, June 2–5, 1986 / [electronic resource] :
edited by Alan L. Selman.
- Berlin, Heidelberg : Springer Berlin Heidelberg, 1986.
- VIII, 404 p. online resource.
- Lecture Notes in Computer Science, 223 0302-9743 ; .
- Lecture Notes in Computer Science, 223 .
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.
9783540398257
10.1007/3-540-16486-3 doi
Computer science.
Computer Science.
Computation by Abstract Devices.
QA75.5-76.95
004.0151
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.
9783540398257
10.1007/3-540-16486-3 doi
Computer science.
Computer Science.
Computation by Abstract Devices.
QA75.5-76.95
004.0151