Half-Sat Problem With Example

Half-SAT = {F | F is a CNF formula with 2n variables and there is a satisfying assignment in which n variables are set to True and n variables are set to False}.
Show that Half-SAT is NP-Hard.

We can show that half-sat is NP-hard by reducing sat to half-sat. We can show that if half-sat has a solution sat also has a solution.

Let T be a turing machine(transducer) which reduces sat to half-sat. T takes F as input.
Let F has variables x1,x2,......xn.
T(F) =  Construct a new CNF formula F' as follows.
            F' will have variables x1,x2,.......xn from F and new variables y1,y2,...........yn such that xi = ‾yi
            If a clause is of the form (x1 U x2), convert it into (x1 U x2) ^( ‾y1  U  ‾y2).
Output(F')
    

Example 1
Let F = (x1 U x2 U ‾x3) and  x1=True,  x2=False, x3= True
F = T U F U T = T
Introduce three new variables y1,y2 and y3 such that
x1 =  ‾y1
x2 =  ‾y2
‾x3 =  y3


F' = (x1 U x2 U ‾x3) ^ (  ‾y1 U ‾y2 U y3).
 x1  = T    y1  =F

x2  = F    y2  =T
x3  = T    y3  =F

Here three variables are assigned True and other three variables are assigned False. Therefore the expression is in half-sat.
Assigning values to F',  F' = ( T U F U T) ^ (T U F U T) =  True.

Hence F' evaluates to  true iff F evaluates to  true.

Let x1=False, x2 = False, x3=False
F=  false U false U false = False
F' = (F U F U F) ^ (F U F U F) = F
Hence F' evaluates to  false iff F evaluates to  false.