Proceedings, Structure in Complexity Theory: Fourth Annual Conference |
Contents
On Polynomial Time Turing and ManyOne | 15 |
On the Theory of Average Case Complexity | 36 |
Hardness vs Randomness A Survey | 54 |
Copyright | |
17 other sections not shown
Common terms and phrases
accepting paths algorithm boolean function Circuit Value circuit value problem 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 oblivious one-way function oracle output p-creative sets P/poly permutation group plexity polynomial hierarchy polynomial time computable polynomial-time PRAM probability problem Proc 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 subset tape techniques Theorem tion Turing degrees Turing machine Turing reductions uniform verifier