ProceedingsSpringer-Verlag, 1989 - Computational complexity |
Contents
The Isomorphism Conjecture Fails Relative to | 2 |
On Polynomial Time Turing and ManyOne | 15 |
PCreative Sets vs PCompletely Creative Sets | 24 |
Copyright | |
27 other sections not shown
Other editions - View all
Common terms and phrases
accepting paths algorithm binary bits circuit value problem complexity classes complexity theory complexity type computable function Computer Science constant construction contains Corollary defined Definition denote deterministic encoding enumeration equivalent example exists exponential fanout finite function f gate graph Hence hierarchy IEEE inductive inference infinite initial segment input integer k-completely creative k-SL Kolmogorov complexity language lattice Lemma linear lower bounds Network Stability nondeterministic NP-complete O(log one-way functions optimal output p-creative sets P/poly partition permutation group plexity polynomial hierarchy polynomial time computable polynomial-time probability proof protocol prove PSPACE queries random oracle recursion theory recursive functions recursive set reducibility relativize requirement RUNSA satisfy scatter-free self-reducibility semicomputable sequence sets in NP simulate space sparse sets stable configuration stage steps strategy strings of length subblock subset tape techniques Theorem tion Turing degrees Turing machine Turing reductions verifier