CODEWITHSUNDEEP
npnp-completesat
Zheyuuu
Zheyuuu

Reputation: 151

Why all NP-complete problems can be reducible to 3-SAT?

When I tried to figure out why halting-problem is NP-hard, I found this. However, there is a statement that confuses me:

We begin by noting that all NP-complete problems are reducible to 3SAT.

Why all NP-Complete problems can be reducible to 3-SAT?

Upvotes: 4

Views: 1722

Answers (2)

WeCanDoItGuys
WeCanDoItGuys

Reputation: 25

I won't try to show how all NP-complete problems (like Travelling Salesman, generalized Sudoku, etc) can be reduced to the satisfiability problem, but I can share my findings from online research for why satisfiability problems can be reduced to 3-SAT.

Definitions:

A satisfiability (SAT) problem is deciding whether a Boolean expression consisting of variables, the operators AND ∧, OR ∨, NOT ¬, and parentheses () can be made TRUE by assigning appropriate TRUE/FALSE values to its variables.

A Boolean expression is in conjunctive normal form (CNF) if it is written as a set of clauses (variables or negated variables linked with OR) that are linked with AND.

3-satisfiability (3SAT) is the satisfiability problem for an expression in CNF where each clause contains 3 literals (variables or negated variables).

Any Boolean expression can be written in conjunctive normal form (though the expression can become exponentially longer) using the rules of Boolean algebra. Below are some rules I found from Wikipedia and ggc-discrete-math.github.io.
associativity a ∨ (b ∨ c) = (a ∨ b) ∨ c a ∧ (b ∧ c) = (a ∧ b) ∧ c
commutativity a ∨ b = b ∨ a a ∧ b = b ∧ a
absorption a ∨ (a ∧ b) = a a ∧ (a ∨ b) = a
identity a ∨ 0 = a a ∧ 1 = a
distributivity a ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) a ∧ (b ∨ c) = (a ∧ b) ∨ (a ∧ c)
complements a ∨ ¬a = 1 a ∧ ¬a = 0
Consensus theorems (a ∨ b) ∧ (¬a ∨ c) ∧ (b ∨ c) ≡ (a ∨ b) ∧ (¬a ∨ c) (a ∧ b) ∨ (¬a ∧ c) ∨ (b ∧ c) ≡ (a ∧ b) ∨ (¬a ∧ c)
De Morgan's laws ¬(a ∧ b) ≡ (¬a ∨ ¬b) ¬(a ∨ b) ≡ (¬a ∧ ¬b)

Example: (a ∧ b) ∨ (c ∧ d) can be written as (a ∨ c) ∧ (b ∨ c) ∧ (a ∨ d) ∧ (b ∨ d)

Stephen Cook (and Leonid Levin) proved in 1971 (and 1973) that every decision problem in NP can be reduced to the SAT problem for an expression in CNF.

Meanwhile, a CNF SAT problem can be reduced to 3SAT, like this:

Source: ratchet and Carlos's answers to SAT to 3SAT reduction

Each clause has 1, 2, 3 or more variables.

The 1 variable clause {a1} can be expanded to {s1, s2, a1}{!s1, s2, a1}{s1, !s2, a1}{!s1, !s2, a1} which can only all be satisfied if a1 is true

The 2 variable clause {a1,a2} can be expanded to {s1, a1, a2}{!s1, a1, a2}

The 3 variable clause can stay as is.

The clause with more than 3 variables {a1,a2,a3,a4,a5} can be expanded to {a1,a2,s1}{!s1,a3,s2}{!s2,a4,a5} with s1 and s2 new variables whose value will depend on which variable in the original clause is true

Upvotes: 0

templatetypedef
templatetypedef

Reputation: 373082

By definition, an NP-complete problem X has the property that every problem Y ∈ NP reduces to X. (This is what NP-hardness means.) Similarly, by definition every NP-complete problem is in NP. Putting these two together, every NP-complete problem reduces to every other, so all NP-complete problems reduce to 3SAT.

Upvotes: 4

Related Questions