Limit search to available items
Book Cover

Title Structure in complexity theory : proceedings of the conference held at the University of California, Berkeley, California, June 2-5, 1986 / edited by Alan L. Selman
Published Berlin ; New York : Springer-Verlag, ©1986


Description 1 online resource (vi, 400 pages) : illustrations
Series Lecture notes in computer science ; 223
Lecture notes in computer science ; 223.
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
Analysis Computational complexity Congresses
Notes Papers presented at the Structure in Complexity Theory Conference
Bibliography Includes bibliographical references and index
Notes Master and use copy. Digital master created according to Benchmark for Faithful Digital Reproductions of Monographs and Serials, Version 1. Digital Library Federation, December 2002. MiAaHDL
digitized 2010 HathiTrust Digital Library committed to preserve pda MiAaHDL
Print version record
Subject Computational complexity -- Congresses
Computational complexity
Algorithmes -- Congrès.
Complexité de calcul (informatique) -- Congrès.
Berkeley <Calif., 1986>
Genre/Form Conference papers and proceedings
Form Electronic book
Author Selman, Alan L
Structure in Complexity Theory Conference (1st : 1986 : Berkeley, Calif.)
ISBN 9783540398257