ProceedingsSpringer-Verlag, 1994 - Computational complexity |
Contents
Approximable Sets | 12 |
Polynomial Time TruthTable Reductions to PSelective Sets | 22 |
On the Query Complexity of Clique Size and Maximum Satisfiability | 31 |
Copyright | |
25 other sections not shown
Other editions - View all
Common terms and phrases
3SAT algorithm approximation assume Balanced-Leaf binary Boolean Boolean circuit circuit Clique collapses complete sets complexity classes Complexity Theory Computer Science configuration conjecture consider constant construction Corollary defined Definition denote deterministic DLOGTIME encoding exists exponential ff(x finite formula FPNP func function f gate given graph guess hard hierarchy holds IEEE implies integer isomorphism leaf languages Lemma length live blocks logspace logspace reductions LogT lower bound many-one many-one reduction martingale MAX3SAT NEXPTIME nodes nondeterministic Note NP-complete NP-hard O(log optimal oracle oracle Turing machine output p-selective set P/poly path Player polynomial polynomial hierarchy polynomial-time predicate prob probabilistic Probabilistic Turing Machine probability Proc proof systems properties Proposition protocol prove PSPACE PSPACE-hard recursive reductions satisfying sequence simulate space bounds strategy strings Structure in Complexity subset tape tion truth-table reducible Turing machine Ultrafilter variables verifier w₁