What people are saying - Write a review
We haven't found any reviews in the usual places.
On the Instance Complexity of NPHard Problems
On Bounded Round MultiProver Interactive Proof Systems
On the Power of Randomness in the Decision Tree Model
18 other sections not shown
accepts algorithm assume binary bits Boolean circuits Boolean function Boolean hierarchy characterization cheatable co-NP collapses complexity classes Complexity Theory computable function Computer Science configuration consider constant construction contains Corollary counting classes decision tree defined Definition denote depth deterministic encoding exists exponential EXPTIME fan-in finite formula Fortnow func G SAT gate groupoid hard sequence Hemachandra IEEE infinite input interactive proof interactive proof system Kolmogorov complexity languages Lemma logarithmic space LOGCFL loglog Logspace lower bound monoid nomial nondeterministic Note NPNP opt-L OptP oracle Turing machine output p-completely p-productive set p-superterse P/poly plexity poly polynomial hierarchy polynomial time computable polynomial-time problems Proc proof systems protocol prove PSPACE quantifiers queries random oracle recursive reducibility relativized resp restricted result self-reducible SIAM simulation Sipser span-L Structure in Complexity subset tally sets Theory of Computing tion Turing machine unbounded fan-in uniform variables verifier