Format:
Online-Ressource (VI, 400 S.)
Edition:
Online-Ausg. Berlin [u.a.] Springer 2006 Springer lecture notes archive
ISBN:
9783540398257
Series Statement:
Lecture notes in computer science 223
Content:
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.
Note:
Literaturangaben
Additional Edition:
ISBN 3540164863
Additional Edition:
ISBN 0387164863
Additional Edition:
ISBN 9783540164869
Additional Edition:
Erscheint auch als Druck-Ausgabe Structure in complexity theory Berlin : Springer, 1986 ISBN 3540164863
Additional Edition:
ISBN 0387164863
Language:
English
Subjects:
Computer Science
,
Mathematics
Keywords:
Komplexitätstheorie
;
Konferenzschrift
DOI:
10.1007/3-540-16486-3
URL:
Volltext
(lizenzpflichtig)
URL:
Volltext
(lizenzpflichtig)
URL:
Volltext
(lizenzpflichtig)
