-- Apr 18 In-Class Exercise Thread
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.
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.