As a result of this lemma, the clique and the knapsack problems are intractable, since those problems can be reduced to the problem for which this theorem applies.
This result can be proven by considering it as a corollary of Fagin's theorem, which states that all properties of second order logic are tractably verifiable using a first-order formula. A reduction named for this result is used to prove the Valiant-Vazirani theorem, which further refines this statement. Using this result to prove the Karp-Lipton theorem shows that "AM equals MA" in the context of the Arthur- Merlin protocol. Proving this statement involves examining legal sets of windows in a tableau to show that there exists a polynomial time sequence of configurations that includes a language's accept state. This statement implies that it is difficult to efficiently convert from conjunctive normal form to disjunctive normal form. As a result of this lemma, the clique and the knapsack problems are intractable, since those problems can be reduced to the problem for which this theorem applies. For 10 points, name this theorem stating that the Boolean satisfiability problem is NP-complete.
This result can be proven by considering it as a corollary of Fagin's theorem, which states that all properties of second order logic are tractably verifiable using a first-order formula.
Cook-Levin theorem