ProceedingsComputer Society Press of the IEEE, 1989 - Computational complexity |
Contents
On Polynomial Time Turing and ManyOne | 15 |
On the Theory of Average Case Complexity | 36 |
Hardness vs Randomness A Survey | 54 |
Copyright | |
16 other sections not shown
Other editions - View all
Common terms and phrases
accepting paths algorithm boolean function branching programs Circuit Value circuit value problem co-NP complexity classes complexity theory computable function Computer Science constant construction Corollary defined Definition denote deterministic encoding enumeration equivalent exists exponential finite function f gate graph Hartmanis Hence IEEE infinite initial segment input integer isomorphic iteration k-completely creative k-SL Kolmogorov complexity language lattice Lemma linear lower bounds nomial nondeterministic NP-complete NP-complete sets one-way function oracle output p-creative sets P/poly permutation group plexity polynomial hierarchy polynomial time computable polynomial-time PRAM probability problem programming system proof properties prove PSPACE quantifier-free query hierarchy random recursion theory recursive functions recursive set reducibility relativize representable requirement RUNSA satisfy self-reducibility sets in NP simulate space sparse set stage steps strings of length structure subset tape techniques Theorem tion Turing degrees Turing machine Turing reductions verifier