What is the definition of an NP-complete problem?
Is the following CNF formula satisfiable? I will use a lower case letter for a positive variable and the corresponding upper case letter for its negative form. For example, X is x-bar. The members of each clause are separated by commas, and the clauses are just listed one after the other.
(x,y,z) (X,Y) (X,Z) (Y,Z)
What conjecture needs to be proved in order to conclude that there is no polynomial time algorithm to solve the clique problem?
Describe the error in the following fallacious "proof" that P is different from NP.
A formula of length n can have at least sqrt(n) different variables. It is satisfiable if some assignment of values to those variables makes it true. But there are 2sqrt(n) assignments of values to the variables, and trying them all takes at least 2sqrt(n) steps. Since 2sqrt(n) grows faster than any polynomial, SAT is not solvable in polynomial time. So SAT is not in P. But SAT is in NP, so P and NP are clearly different classes.
(This argument has actually been proposed before. The first recorded instance was by a group of Russian mathematicians in 1959; they quickly realized their error.)
NAE-3-SAT is the set {f | f is a formula that can be satisfied in such a way that each clause has at least one true literal and at least one false literal. Prove that NAE-3-SAT is in NP. (NAE stands for "not all equal". It turns out that NAE-3-SAT is NP-complete, but you are not being asked to show that here.)
The subgraph isomorphism problem is as follows.
Input. Two undirected graphs G and H.
Question. Is H isomorphic to a subgraph of G? That is, can you remove zero or more vertices and zero or more edges from G and obtain a graph that has the same structure as H?
Show that the clique problem polynomial-time reduces to the subgraph isomorphism problem.