Post your solution to the Apr 18 In-Class Exercise to this thread.

Best,

Chris

To show L is NP-Complete we can show that 3SAT can be reduced to L. A given OR clause in 3SAT has 3 literals we will name v1, v2, v3. Introduce a new literal for every v1,v2 pair that is the value of (v1 OR v2). Call this new literal v4i where i is the index of this clause. Now, create a new literal with value false, call this F. Rewrite every clause of the 3SAT problem with the literals (v4i, v3, F).

To show that L is NP-complete, we need to show that 3SAT, which is NP-complete, can be reduced to L and that L is in LP. First L is in NP by the same argument that showed CIRCUIT-SAT in NP ---(1) For reduction, in 3SAT we have (l_i_11 OR l_i_12 OR l_i_13) AND (l_i_21 OR l_i_22 OR l_i_23) AND .... AND (l_m_11 OR l_m_12 OR l_m_13), now lets assume a new variable C_k such that C_i_j = (l_i_11 OR l_i_12). So we can write one clause above as (C_1_1 OR l_1_3 OR F) AND (C_2_1 OR l_2_3 OR F) AND .... AND (C_m_1 OR l_m_3 OR F). This is our language L. Thus we have reduced 3SAT to L ---(2) From (1) & (2), we can say that L is NP-complete.

Given L = {FF is a 3-CNF formula which is satisfiable by an assignment which makes at least one literal false in every clause}.

We can prove that L is NP-complete by showing that 3SAT(another NP-complete problem) can be reduced to L.

The 3SAT contains the ANDs of 8 OR's each with 3 literal inputs.

Consider the inputs to each OR gate as w,x and y, Create a new literal z which is (w V x) and the other literal as signal F(False). ---- Now every clause can be rewritten as (z,y,F) which is the language L.

Hence L is NP-complete.

<nowiki> let <C> be an instance of CIRCUIT-SAT. (X1 and -X7 and X15) or (-X1 and X2 and X3) there should be one variable where the value should be a negation of original variable in another set.Given three values X1, X2 and X3, we can introduce 4th value X4 such as negation of this value X4 is false F. Hence 3SAT problem can be shown with arguments X3, X4, and F. </nowiki>

<nowiki> ^ ^ ^ ^ ^ ^ ^ ^ let <C> be an instance of CIRCUIT-SAT. (X1 and -X7 and X15) or (-X1 and X2 and X3) there should be one variable where the value should be a negation of original variable in another set.Given three values X1, X2 and X3, we can introduce 4th value X4 such as negation of this value X4 is false F. Hence 3SAT problem can be shown with arguments X3, X4, and F.</nowiki>

If 3 SAT can be reduced to L, we can show that L is NP-Complete. If we consider a single clause in 3SAT, it will have 3 literals, v1,v2 and v3. Now we can introduce a whole new literal, which has the value v1 or v2. This can be called v(i), where i denotes the index opf the clause within the statement. We can create another variable with the value false and call it F. Now we can rewrite every clause within the 3SAT problem as (v(i),v3,F), thus reducing the problem.

For a language L to be NP-complete, it must be in NP along with every language L' that it reduces to.

We can show that 3SAT reduces to L if we consider that one of the literals in each clause of L is false (F). If we create a new literal that is the value of v1 or v2 in the clause (vi) we can write each clause as (vi, v3, F). Thus we show that 3SAT reduces to L.

1. For L to be NP-Complete, we need to show that 3SAT can be reduced to L. A single clause in 3SAT will have 3 literals p, q, r.
2. If we introduce a new literal with value p or q, we can term it p(i), where i denotes the index of the clause in the statement.
3. Now we create another variable with the value "false" and call it F.
4. Hence, we can rewrite every clause within the 3SAT problem as (p(i), r, F), thereby reducing the problem to L and proving it is NP-Complete.

<nowiki> 3SAT is an NP-complete problem. If 3SAT can be reduced to L, We can prove that L is NP-complete problem. The 3SAT contains the ANDs of 8 OR clauses, with 3 literal in each clause. Consider the inputs to each OR gate as a,b and c which makes a clause. Now Create a new literal d which is (a V b) and the other literal as signal F(False). Now every clause can be rewritten as (c,b,F) which is the language L given in the problem. Now, since 3SAT is an NP-complete problem and So L also is NP-complete.

</nowiki>