UID:
almahu_9947920996202882
Format:
VIII, 404 p.
,
online resource.
ISBN:
9783540398257
Series Statement:
Lecture Notes in Computer Science, 223
Note:
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.
In:
Springer eBooks
Additional Edition:
Printed edition: ISBN 9783540164869
Language:
English
DOI:
10.1007/3-540-16486-3
URL:
http://dx.doi.org/10.1007/3-540-16486-3
