Double SAT is NP Complete

Problem Statement: Given a formula f, the problem is to determine if f has two satisfying assignments.

Explanation: An instance of the problem is an input specified to the problem. An instance of Double Sat problem is a boolean formula f. Since an NP-complete problem is a problem which is both NP and NP-Hard, the proof or statement that a problem is NP-Complete consists of two parts:

1. The problem itself is in NP class.
2. All other problems in NP class can be polynomial-time reducible to that.
   (B is polynomial-time reducible to C is denoted as B ≤ P^C)

If the 2nd condition is only satisfied then the problem is called NP-Hard.
But it is not possible to reduce every NP problem into another NP problem to show its NP-Completeness all the time. Therefore to show a problem is NP-complete, then prove that the problem is in NP and any NP-Complete problem is reducible to that i.e., if B is NP-Complete and B ≤ P^C . For C in NP, then C is NP-Complete. Thus, it can be verified that the Double SAT problem is NP-Complete using the following propositions:

1. Double Sat is in NP:
   If any problem is in NP, then it is given a ‘certificate’, which is a solution to the problem and an instance of the problem(a formula f) then it can identify (whether the solution is correct or not) certificate in polynomial time. This can be done by giving a set of satisfying assignments for the variables in f, and verify if each clause is satisfied in f.
2. Double Sat is NP-Hard:
   In order to prove double sat is NP-Hard then reduce a known NP-Hard problem, 3-SAT (in this case) to our problem.
   This can be done by:
   Given a 3-CNF function g then create a boolean function f by adding a pair of literals (x V x’) to each clause of f, where x is an additional variable. This reduction can work in polynomial time.
   Now, the following two propositions hold:
   • If g is unsatisfiable, then some clause of g must be FALSE, and therefore, f must also be unsatisfiable.
   • If 3-SAT formula g is satisfiable, then using the same set of assignment variables comprised in g, we can have both x=0 and x=1 as the valid assignments to g.

Therefore, Double-SAT Problem is NP-Complete.