Proceedings, Structure in Complexity Theory: Fourth Annual Conference
IEEE Computer Society Press, 1989 - Computational complexity - 271 pages
Papers from the Fourth Annual Conference, held June 1989, Eugene, OR. Twenty-five papers on recent research in the field. Acidic paper; no index. Annotation copyright Book News, Inc. Portland, Or.
37 pages matching output in this book
Results 1-3 of 37
What people are saying - Write a review
We haven't found any reviews in the usual places.
On Polynomial Time Turing and ManyOne
On the Theory of Average Case Complexity
Hardness vs Randomness A Survey
17 other sections not shown
accepting paths algorithm boolean function Circuit Value circuit value problem complexity classes complexity theory complexity type computable function Computer Science consider constant construction contains Corollary creative sets defined Definition denote deterministic encoding enumeration equivalent example exists exponential finite function f gate given graph Hartmanis Hence IEEE infinite initial segment input instance integer isomorphic iteration Kolmogorov complexity language lattice Lemma linear logarithmic lower bounds nomial nondeterministic oblivious one-way function oracle output p-completely p-completely creative p-creative P/poly permutation group plexity polynomial time computable polynomial-time probability problem Proc program-size complexity programming system properties protocol prove PSPACE quantifier-free query hierarchy random recursion theory recursive function recursive set reducibility relativize representable requirement satisfy scatter-free self-reducibility sets in NP simulate Solomonoff space sparse set stage steps strings of length subset tape techniques tion Turing degrees Turing machine Turing reductions uniform verifier