Satisfiability ≥P 3-SAT

 

Satisfiability ≥_P 3-SAT

Having established that satisfiability is NP-Complete, we can show that 3-SAT is. 3-SAT is the version of SAT where there are only ever three literals per clause.

To show that 3-SAT is NP-Complete, we use the fact that SAT is NP-Complete and show that 3-SAT can be reduced to SAT in polynomial time. This means that if we had a polynomial time solution for 3-SAT, we could use it to solve SAT in polynomial time, and therefore all problems in NP.

To reduce SAT to 3-SAT, we can take any boolean formula in conjunctive normal form and transform it into an equivalent formula in 3-SAT form by adding auxiliary variables and clauses as needed. This process can be done in polynomial time, so we have shown that 3-SAT is NP-Complete.

Other examples of NP-Complete problems include the knapsack problem, the partition problem, and the vertex cover problem. These problems are all known to be at least as hard as any problem in NP, and no efficient solutions are known for them.

So if we take a general SAT formula, each clause has either less than 3, exactly 3, or more than 3 literals in it.

●     If it has exactly 3, do nothing

●     If it has less than 3, simply repeat one of the literals (it makes absolutely no difference to the truth assignment)

●     If it has more than three...

●     We can split the clause into smaller clauses, each with exactly three literals. For example, the clause (A ∨ B ∨ C ∨ D ∨ E) can be split into the following three clauses: (A ∨ B ∨ C), (A ∨ B ∨ D), and (A ∨ B ∨ E). This process is known as reduction.

●     By showing that any instance of SAT can be reduced to an instance of 3-SAT in polynomial time, we can conclude that 3-SAT is NP-Complete.

●     Similarly, we can show that other problems are NP-Complete by reducing them to other NP-Complete problems. This process is known as showing NP-hardness. For example, the subset sum problem is NP-Hard because it can be reduced to 3-SAT in polynomial time.

Satisfiability ≥_P 3-SAT

If a clause has more than three literals:

●        e.g. (a ∨ ¬b ∨ c ∨ ¬d ∨ e ∨ ¬f)

●        We can turn it into a series of 3-literal clauses with the use of some extra literals l

●        (a ∨ ¬b ∨ l₁) ∧ (¬l₁ ∨ c ∨ l₂) ∧ (¬l₂ ∨ ¬d ∨ l₃) ∧ (¬l₃ ∨ e ∨ ¬f)

This process is called reduction, and it allows us to turn any instance of SAT into an equivalent instance of 3-SAT in polynomial time. Therefore, we can say that SAT ≥P 3-SAT, which means that 3-SAT is also NP-Complete.

Now, we can use this process of reduction to show that many other problems are NP-Complete as well. Essentially, if we can show that a problem A reduces to SAT in polynomial time, and we already know that SAT is NP-Complete, then we can conclude that problem A is also NP-Complete. This is a powerful tool for showing that many problems are NP-Complete, and it is the basis for the concept of NP-Completeness.

It should be clear that this increases the total size of the problem by no more than a factor of 3 (so the transformation is polynomial time)

It should also be clear that any satisfying assignment for the original clause will also be a satisfying assignment for the transformed 3-SAT formula, and vice versa. This means that the 3-SAT problem is at least as hard as the SAT problem, which we already know to be NP-Complete. Therefore, 3-SAT is also NP-Complete.

Since it should be plain that 3-SAT is in NP, then 3-SAT is NP-Complete.

We can show that 3-SAT is NP-complete by proving that it is in NP (a "yes" instance can be verified in polynomial time by using a witness, which is a satisfying assignment) and that it is at least as hard as any other problem in NP. We do this by showing that we can transform any other problem in NP into an equivalent instance of 3-SAT in polynomial time. This means that if we can find an efficient solution to 3-SAT, we can use it to solve all other problems in NP efficiently as well.

3-SAT ≥_P Independent Set

The independent set problem asks, given a graph G = (V, E), if there is a subset S of V such that no two nodes of S are adjacent and |S| > k.

It is unknown whether the independent set problem is in P, NP, or co-NP. It is not known whether it is possible to find an independent set of a given size in polynomial time, or whether it is possible to verify the existence of an independent set of a given size in polynomial time. The independent set problem is one of many problems that are not known to be in any of the classes P, NP, and co-NP.

For any instance of 3-SAT, we can easily produce an equivalent instance of independent set, whereby the 3-SAT formula is satisfiable iff there is an independent set of size n.

To do this, we create a graph where each variable in the 3-SAT formula is represented by two nodes in the graph (one for each possible value). Then, for each clause in the 3-SAT formula, we connect the two nodes representing the negation of each literal in the clause. This means that if a node representing a literal is included in the independent set, then the negation of that literal cannot be included. Therefore, if we can find an independent set of size n (where n is the number of variables in the 3-SAT formula), then we have found a satisfying assignment for the 3-SAT formula.

Since independent set is in NP (a "yes" instance can be verified in polynomial time by using a witness, which is the independent set itself), and it can be reduced to 3-SAT in polynomial time, independent set is also NP-Complete.

First, we arrange each clause into a triangle of nodes and label each of them with their literals, then we connect any two opposites (such as a and ¬a with an edge).

We can then use this graph to check for the existence of an independent set. If there is an independent set of size n (where n is the number of clauses in the 3-SAT formula), this means that there exists a truth assignment that satisfies all of the clauses, because no two nodes in the independent set are connected by an edge. Conversely, if the 3-SAT formula is satisfiable, this means that there exists a truth assignment that satisfies all of the clauses, and this truth assignment can be represented by an independent set of size n in the graph. Therefore, the 3-SAT problem is polynomial-time reducible to the independent set problem, which means that the independent set problem is NP-hard.

It is not known whether the independent set problem is in NP, so it is not known whether it is NP-Complete. However, it is believed to be NP-hard, which means that it is at least as hard as the hardest problems in NP.

An example follows...

3-SAT ≥_P Independent Set

First, create triangles:

Then connect opposites:

If there is a satisfying assignment, it will be possible to select one member of S from each clause without it being connected to another member of S.

3-SAT ≥_P Vertex Cover

 

The vertex cover problem (in decision form) asks, given a graph G = (V, E) is there a subset S of V such that every edge in E is incident on a vertex of S and |S| < k.

To show that the independent set problem is NP-Complete, we can reduce it to the vertex cover problem. The vertex cover problem is defined as follows: given a graph G = (V, E), find a subset S of V such that for every edge (u, v) in E, at least one of u or v is in S, and |S| is minimized.

To reduce the independent set problem to the vertex cover problem, we can consider the complement of the given graph G, which is a graph G' = (V', E') where V' = V and E' = {(u, v) | (u, v) is not in E}. Then, we can find a vertex cover in G' by finding an independent set in G, and the size of the independent set in G will be equal to the size of the vertex cover in G'.

Since the vertex cover problem is known to be in NP, this reduction shows that the independent set problem is also in NP. Thus, the independent set problem is NP-Complete.

For each variable v in our 3-SAT formula, we create two nodes and label them v and ¬v and join them with an edge.

(a ∨ b ∨ ¬c) ∧ (¬a ∨ ¬b ∨ c) ∧ (b ∨ ¬c ∨ d)

Then for each clause, we produce a node for each literal and connect them in a triangle. Finally, connect nodes with the same label.

We know that at least one of the node pairs along the top must be in the vertex cover (or else the edges in between won’t be covered). Also, at least 2 out of 3 of the nodes in the triangles at the bottom must be in the cover.

So, if we can find a vertex cover of size k, we can use this to satisfy the 3-SAT formula by setting the variables in the covered nodes to true and the ones in the uncovered nodes to false. This means that the independent set problem is NP-Complete.

The vertex cover problem is the opposite of the independent set problem, it asks whether there is a subset of nodes in a graph such that all edges are incident to at least one node in the subset. It is easy to see that the vertex cover problem is in NP, because a "yes" instance (a vertex cover) can be verified in polynomial time by simply checking that all of the edges are incident to at least one node in the subset. Since the independent set problem reduces to the vertex cover problem, it follows that the vertex cover problem is also NP-Complete.

It turns out that if the formula is not satisfiable, more vertices need to be added to the cover - and if it isn’t they don’t.

This means that the size of the vertex cover is equal to the number of variables in the 3-SAT formula plus a constant if the formula is not satisfiable, and equal to the number of variables plus another constant if the formula is satisfiable. This means that the independent set problem is in NP, and therefore it is NP-Complete.

So the formula is satisfiable iff there is a vertex cover with size n+2c or less, where n is the number of variables and c the number of clauses.

This means that the vertex cover problem is NP-Complete, because it is in NP (a "yes" instance of the problem can be verified in polynomial time by using a witness, which is the vertex cover itself) and it is NP-hard (every problem in NP can be reduced to it in polynomial time).