Chomsky Hierarchy Diagram for Languages.

The diagram shows how different classes of languages such as regular, context free, context sensitive, P, NP, PSAPACE, NPSPACE, EXPTIME, NEXPTIME, EXPSPACE, ACCEPTABLE, DECIDABLE, CO-ACCEPTABLE etc are related to each other.

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.

NP- complete Problems with variations

K-clique                           video

•    half-clique
•   quarter-clique
•   sub-graph  isomorphism
•   Independent set                  video
•   vertex cover                       video
•   Exact Cover                       video

Hamiltonian Path                   video lecture

• Does a hamiltonian path exist in G.
• Does a hamiltonian path exist from node s to t
• k-link path 
• Hamiltonian Circuit       video

SAT Problems                    video

• TRUE-SAT
• DOUBLE-SAT
• 3SAT
• HALF-SAT
• not equal to 3SAT

Subset Sum Problem              video

• Partition                       video
• Multiset                        video

3-COLOR

Half Clique Problem with examples ( Complexity theory )

Half-clique problem is described as follows. Given a graph G with n number of vertices, does there exist a clique of G consisting of exactly  half the nodes of G? Show that HALF-CLIQUE is NP-hard by reducing CLIQUE to  HALF-CLIQUE.

 Let f be a transducer which does the reduction.

f(G,k) =  Construct G' as follows
              Add n more vertices to G.
              Select n-k of the newly added vertices, connect them to each other and to all  original vertices in G.
             
Output (G')

Here adding n-k vertices to G can be done in polynomial time. So reduction is done in polynomial time.
Yes Instance

In the following example G has 5 nodes. Let k=3. This is a yes instance since G has a clique of k=3( nodes A,B and E).

Construct G' by adding 5 more nodes (F,G,H,I,J)  to graph G. Connect 5-3=2 of them to each other and to original nodes of G.

G' has five-clique (A,B,E,F and G). 
G' will not have 5-clique unless G already has a 3 clique.

No Instance

Try yourself.:

Remove any of the edges forming 3 clique and try to construct G'. Check whether G' can have a 5-clique.


Clique can be reduced to any fractionof clique using the same logic. To solve (1/m)th clique, add (m-1)n vertices to graph G and connect n-k vertices.
For example, to solve quarter-clique, add 3n vertices to G and fully connect n-k new vertices.