Vipul: Created page with "==Statement== ===Statement in terms of complexity classes=== The theorem has the following equivalent formulations. Pick any equivalent formulation of the conditional -- the th..."

2010-08-13T00:52:19Z

Created page with "==Statement== ===Statement in terms of complexity classes=== The theorem has the following equivalent formulations. Pick any equivalent formulation of the conditional -- the th..."

New page

==Statement==

===Statement in terms of complexity classes===

The theorem has the following equivalent formulations. Pick any equivalent formulation of the conditional -- the theorem states that that implies any equivalent formulation of the conclusion.

Equivalent formulations of the conditional:

# [[fact about::NP]] is contained in [[fact about::P/poly]]
# The problem [[fact about::3-SAT]] is contained in [[fact about::P/poly]].
# [[fact about::co-NP]] is contained in [[P/poly]].

Equivalent formulations of the conclusion:

# The class <math>\Sigma_2P</math> (i.e., [[fact about::Sigma2P]]) is self-complementary, i.e., it equals its complementary class <math>\Pi_2P</math> (i.e., [[fact about::Pi2P]]).
# [[fact about::PH]] collapses to <math>\Sigma_2P</math>.
# [[fact about::PH]] collapses to <math>\Pi_2P</math>.

===Loose philosophical statement===

Deterministic solution of a problem using length-specific advice <math>\to</math> Nondeterministic solution by pushing the advice inside an additional existential quantifier

==Related facts==

* [[Adleman's theorem]] states that [[BPP]] is in [[P/poly]].
* The Karp-Lipton theorem and Adleman's theorem together imply that [[BPP equals Sigma2P implies BPP equals PH]]

Karp-Lipton theorem - Revision history

Vipul: Created page with "==Statement== ===Statement in terms of complexity classes=== The theorem has the following equivalent formulations. Pick any equivalent formulation of the conditional -- the th..."