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
Other editions - View all
accepting paths algorithm boolean function Circuit Value circuit value problem co-NP 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 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 permutation group plexity polynomial hierarchy 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