Satisfiability (SAT)

 

Satisfiability (SAT)

Cook’s Theorem demonstrates that any NP problem can be transformed into an instance of SAT in polynomial time.

a brief overview of the proof:

First, we need to understand what it means for a problem to be in NP. A problem is in NP if there exists a polynomial-time algorithm for verifying solutions to the problem, given a witness. In other words, if we are given a solution to the problem and a witness, we can check whether the solution is correct in polynomial time.

The SAT problem is defined as follows: given a Boolean formula in conjunctive normal form (CNF), determine whether there exists a truth assignment for the variables in the formula such that the formula evaluates to true. This problem is a decision problem, because it involves determining whether a given instance has a certain property (a truth assignment that makes the formula evaluate to true).

Cook's Theorem states that if any problem in NP can be reduced to the SAT problem in polynomial time, then SAT is NP-Complete. In other words, if we can find a polynomial-time algorithm for transforming an instance of any problem in NP into an instance of SAT, and if we can solve the resulting SAT instance in polynomial time, then SAT is NP-Complete.

To prove Cook's Theorem, we need to show that the SAT problem is in NP and that any problem in NP can be reduced to the SAT problem in polynomial time. The fact that SAT is in NP follows from the definition of NP, as we can verify solutions to the SAT problem in polynomial time using a witness (the truth assignment). To show that any problem in NP can be reduced to the SAT problem in polynomial time, we need to use the concept of a nondeterministic Turing machine.

A nondeterministic Turing machine is a theoretical model of computation that can "guess" the next step in its computation. This allows it to solve problems in NP, because it can try different guesses and check their validity in polynomial time. Using a nondeterministic Turing machine, we can transform any problem in NP into an instance of SAT in polynomial time, by encoding the computation of the Turing machine as a Boolean formula. This completes the proof of Cook's Theorem.

SAT asks the question, given a boolean formula in conjunctive normal form (an and of ors) does any combination of inputs evaluate to true. Such a combination is called a satisfying assignment.

●     e.g. (a ∨ ¬b ∨ c) ∧ (a ∨ b ∨ ¬c) ∧ …

●     For example, consider the formula (a ∨ ¬b) ∧ (¬a ∨ b). This formula has two satisfying assignments: {a=True, b=True} and {a=False, b=False}.

●     To prove that SAT is NP-Complete, Cook first showed that it is a member of NP. To do this, he showed that given a formula and a proposed satisfying assignment, it can be verified in polynomial time whether the assignment is indeed a satisfying assignment for the formula.

●     Cook then showed that if any problem in NP can be efficiently reduced to SAT, then SAT is NP-Complete. In other words, if there is an efficient way to transform instances of any NP problem into instances of SAT, and if there is an efficient way to transform solutions to those SAT instances back into solutions for the original problem, then SAT is NP-Complete. This is known as the NP-Completeness of SAT.

●     Since the proof of Cook's Theorem, many other problems have been shown to be NP-Complete, including subset sum and the traveling salesman problem.

We say that all problems in NP reduce to SAT in polynomial time, and this can be donated by the symbol ≥_P. As in NP ≥_P SAT

This means that any problem in NP can be transformed into an instance of the SAT problem in polynomial time. Additionally, if there is a polynomial-time solution to the SAT problem, then there is a polynomial-time solution to all problems in NP. This is why the SAT problem is considered to be the "hardest" problem in NP. If we can find an efficient solution to the SAT problem, then we can use it to solve all of the other problems in NP efficiently as well.