Yioop - PHP Search Engine

-- Apr 18 In-Class Exercise Thread

In order to prove that L is NP-Complete we can show that 3SAT, which is also NP-Complete can be reduced to L. Considering a single clause in 3SAT with 3 literals (v1, v2, v3), We create a new literal that has value v1 OR v2. We do this for each v1,v2 pair = > let us call this new literal vi where i is the index of the clause We now create a new literal with value = False(let's call this F) Now we can re-write every clause of the 3-SAT problem with the literals (vi, v3, F) Hence, 3-SAT is reduces to L

-- Apr 18 In-Class Exercise Thread

 For a given L where <F>|<F> is a 3-CNF, let the language comprise of <x1, x2 , x3> literal with relationship : <x1 and x2> OR <x3>. Now lets add a new literal x4 with a property x4 = ~x1 to the 2nd term. the language definition now becomes:
 <x1 and x2> or <x3 and x4>
 For the above definition because of the negation property of x4 = ~x1 one of literals will be false in every iteration. Hence the above language definition is NP-complete.

(Edited: 2018-04-23)

For a given L where <F>|<F> is a 3-CNF, let the language comprise of <x1, x2 , x3> literal with relationship : <x1 and x2> OR <x3>. Now lets add a new literal x4 with a property x4 = ~x1 to the 2nd term. the language definition now becomes: <x1 and x2> or <x3 and x4> For the above definition because of the negation property of x4 = ~x1 one of literals will be false in every iteration. Hence the above language definition is NP-complete.

-- Apr 18 In-Class Exercise Thread

 If 3-SAT can be reduced to L in polynomial time then we can say that L is NP-Complete.

To reduce 3-Sat to L, for every clause in L say (x1 V x2 V x3) add a new clause (x4 V x3 V F) with x4 = (x1 V x2). This would reduce 3-SAT to L satisfying the constraints of L (at least one literal of the clause is F)(Edited: 2018-04-23)

If 3-SAT can be reduced to L in polynomial time then we can say that L is NP-Complete. To reduce 3-Sat to L, for every clause in L say (x1 V x2 V x3) add a new clause (x4 V x3 V F) with x4 = (x1 V x2). This would reduce 3-SAT to L satisfying the constraints of L (at least one literal of the clause is F)

-- Apr 18 In-Class Exercise Thread

 L can be proved to be a NP-complete problem. If 3SAT can be reduced to L, then it can be proved to be NP- complete too.
 
 The 3SAT contains <x1 and x2> or <x3 and x4>

 Consider the inputs to each OR gate x1, x2 and x3 which make a clause. 
 (x1 and x2) or x3

 A new literal d is created which is (x1 V x2) and the other literal as signal F = False. 
 Now every clause can be rewritten as (xi,x3,F) which is the language L given in the problem.

L can be proved to be a NP-complete problem. If 3SAT can be reduced to L, then it can be proved to be NP- complete too. The 3SAT contains <x1 and x2> or <x3 and x4> Consider the inputs to each OR gate x1, x2 and x3 which make a clause. (x1 and x2) or x3 A new literal d is created which is (x1 V x2) and the other literal as signal F = False. Now every clause can be rewritten as (xi,x3,F) which is the language L given in the problem.

-- Apr 18 In-Class Exercise Thread

Showing we can reduce 3SAT to L, we can prove that L is NP-complete.

To show that 3SAT reduces to L if we consider that one of the literals in each clause of L is false (F) and we create a new literal that is the value of v1 or v2 in the clause `v_{y}` we can write each clause as (`v_{y}`, v3, F) which is in L. Thus we can conclude that L is an NP-Complete since 3SAT is NP-Complete

(Edited: 2018-04-23)

Showing we can reduce 3SAT to L, we can prove that L is NP-complete. To show that 3SAT reduces to L if we consider that one of the literals in each clause of L is false (F) and we create a new literal that is the value of v1 or v2 in the clause @BT@v_{y}@BT@ we can write each clause as (@BT@v_{y}@BT@, v3, F) which is in L. Thus we can conclude that L is an NP-Complete since 3SAT is NP-Complete