UID:
edocfu_9959186095302883
Umfang:
1 online resource (VIII, 404 p.)
Ausgabe:
1st ed. 1986.
Ausgabe:
Online edition Springer Lecture Notes Archive ; 041142-5
ISBN:
3-540-39825-2
Serie:
Lecture Notes in Computer Science, 223
Anmerkung:
Bibliographic Level Mode of Issuance: Monograph
,
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.
,
English
In:
Springer eBooks
Weitere Ausg.:
ISBN 3-540-16486-3
Sprache:
Englisch
DOI:
10.1007/3-540-16486-3
URL:
http://dx.doi.org/10.1007/3-540-16486-3
