Structure in Complexity Theory
Springer Berlin (Verlag)
978-3-540-16486-9 (ISBN)
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.
| Erscheint lt. Verlag | 1.5.1986 |
|---|---|
| Reihe/Serie | Lecture Notes in Computer Science |
| Zusatzinfo | VIII, 404 p. |
| Verlagsort | Berlin |
| Sprache | englisch |
| Maße | 155 x 235 mm |
| Gewicht | 667 g |
| Themenwelt | Informatik ► Software Entwicklung ► User Interfaces (HCI) |
| Mathematik / Informatik ► Informatik ► Theorie / Studium | |
| Schlagworte | arithmetic • Automata • Complexity • Complexity theory • Function • Hardware • Informatik • Morphism • Optimization • Probability • Topology |
| ISBN-10 | 3-540-16486-3 / 3540164863 |
| ISBN-13 | 978-3-540-16486-9 / 9783540164869 |
| Zustand | Neuware |
| Haben Sie eine Frage zum Produkt? |
aus dem Bereich
