Structure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986 by Alan L. SelmanStructure in Complexity Theory: Proceedings of the Conference held at the University of California, Berkeley, June 2-5, 1986 by Alan L. Selman

Structure in Complexity Theory: Proceedings of the Conference held at the University of California…

EditorAlan L. Selman

Paperback | May 1, 1986

Pricing and Purchase Info

$140.64 online 
$154.95 list price save 9%
Earn 703 plum® points

Prices and offers may vary in store

Quantity:

In stock online

Ships free on orders over $25

Not available in stores

Title:Structure in Complexity Theory: Proceedings of the Conference held at the University of California…Format:PaperbackDimensions:401 pages, 9.25 × 6.1 × 0.68 inPublished:May 1, 1986Publisher:Springer Berlin HeidelbergLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:3540164863

ISBN - 13:9783540164869

Look for similar items by category:

Reviews

Table of Contents

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.