In this problem assume that P has just been proven equal to NP, and so you have

Question

In this problem assume that P has just been proven equal to NP, and so you have a polynomial time algorithm A that decides 3-SAT; that is, it takes in a logical formula written in 3-SAT form ((x_1 Vx_2 V-x_3) (x_1 x_2 -x_3) ...), and it tells you whether or not a satisfying assignment exists for that formula (you also have a million dollars because you solved P = NP, but that's a different story...) So you have an algorithm A that tells you whether or not a satisfying solution exists for a logic formula, but you don't have one that tells you what exactly that satisfying solution is. For this problem, write a polynomial-time algorithm that finds a satisfying solution to an instance of 3-SAT, given that you have a polynomial-time algorithm A you can run that tells you whether or not a solution exists to an instance of 3-SAT.

Explanation / Answer

The significance of polynomial-time algorithms is that they are usually found to be computationally feasible, even for large input graphs. By contrast, algorithms whose complexity is exponential in the size of the input have running times which render then unusable even on inputs of moderate size.

Given polynomial algorithm A so by Cook’s theorem it can be proved that NP complete problems can be solved . More precisely, this theorem proved that the satisfiability problem for boolean formulae is NP-complete.

Cooks theorem: The problem SAT is NP-complete

Proof:

This is done by a simple reduction from SAT

A Boolean formula is a 3cnf-formula if it is a formula in Conjuctive Normal Form, and every clause has exactly 3 literals.

Let 3SAT be the language { áFñ| F is a satisfiable 3cnf-formula }

To reduce CNF-SAT to 3SAT, we convert a cnf-formula F into a 3cnf-formula F’, with F is satisfiable ó F’is satisfiable

Firstly, let C1 ,C2 ,…,Ck be the clauses in F. If F is a 3cnf-formula, just set F’to be F. Otherwise, the only reasons why F is not a 3cnf-formula are:

• Some clauses Ci has less than 3 literals

• Some clauses Ci has more than 3 literals.

For each clause that has one literal, say L1 , we change it into (L1 _ L1 _ L1 ) è Thus, if F’is satisfiable, the value of L1 must be 1

For each clause that has two literals, say (L1 _ L2 ), we change it into (L1 _ L2 _ L1 ) è Thus, if F’is satisfiable, the value of (L1 _ L2 ) must be 1.

For each clause that has more than three literals, say (L1 _ L2 _ …_ Lm), we use new variables zi , and replace the clause by (L1 _ L2 _ z1 ) ^ (:z1 _ L3 _ z2 ) ^ (:z2 _ L4 _ z3 ) ^ …^ (:zm-3 _ Lm-1 _ Lm)

Thus, if F’is satisfiable, the value of (L1 _ L2 _ …_ Lm) must be 1

Finally, for each clause that has three literals, no change to it By our construction of F’ , F is satisfiable ó F’is satisfiable (why??) Also, the above conversion takes polynomial time (why??) So, CNF-SAT is polynomial time reducible to 3SAT.

Thu 3-SAT is NP-complete.

The given formula is in CNF.Here is the given logical formula.

Assuming P = NP, we have a polynomial time algorithm deciding SAT. To produce a satisfying assignment for a satisfiable formula , substitute x1 = 0 and x1 = 1 in and and test the satisfiability of the two resulting formulas 0 and 1. At least one of these must be satisfiable because is satisfiable.

If 0 is satisfiable, pick x1 = 0; otherwise 1 is satisfiable, pick x1 = 1. That gives the value of x1 in a satisfying assignment. Make that substitution permanent and determine a value for x2 in a satisfying assignment in the same way. Continue until all variables been substituted.

Here we will show that although 3SAT is a subset of SAT, it has the same complexity: SAT p 3SAT. We will start with a formula in CNF form and obtain a 3CNF formula.

Consider one clause of a formula, for example, (¬x1 x2 ¬x3). We want to convert this clause into a 3CNF formula. The idea is to introduce a new variable y encoding the last two literals of the clause. Then, the formula becomes (¬x1 x3 y) (y (x1 ¬x3)).

Now, opening the and bringing it into CNF form, we obtain (¬x1 x3 y) (¬y x41 ¬x3) (y ¬x2) (y x3). Now apply this transformation to the formula until every clause has at most 3 literals. Now it remains to be shown that the transformation can be done in polynomial time. For every extra literal in a clause there needs to be a y introduced.

Therefore, since there can be as many as n literals in a clause, there can be as many as n2 such replacements per clause, for m clauses, and each introducing 3 new clauses.

Therefore, the new formula will be of size at most 4nm, which is definitely a polynomial in the size of the original formula. Moreover, each step takes only constant time. Therefore, f is computable in polynomial time.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.