What is the definition of an NP-complete problem?
Decision problem A is NP-complete if A is in NP and for every X in NP, X reduces to A in polynomial time.
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)
Yes, this is satisfiable. For example, choose x = F, y = F, z = T.
What conjecture needs to be proved in order to conclude that there is no polynomial time algorithm to solve the clique problem?
You would need to prove that P is different from NP.
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.)
The flaw is that it presupposes that an algorithm for testing satisfiability must work by trying all possible values for the variables. All this shows is that this one algorithm does not run in polynomial time. It does not show that no other algorithm for SAT can exist that does run in polynomial time.
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.)
We need a short, easy to check certificate. Let a certificate be an assignment of true/false to each variable. To check the certificate, check that each clause has at least one true literal and at least one false literal, using the given assignment of values for the variables. Each clause can be tested in just a little more than the time it takes to look up three values in the table of variable bindings, and is clearly computable in polynomial time.
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.
A graph is complete if all possible edges are present; that is, every vertex is adjacent to every other vertex. Given an input (G,k) to the clique problem, first check that G has at least k vertices and at least (k choose 2) edges. If it doesn't, then G clearly cannot contain a clique of size k, so just make f(G,k) = (A,B) where A is a graph with no vertices and B is a graph with one vertex. If k is small enough to be sensible, then build a complete graph C having k vertices, and let f(G,k) = (G,C).
Clearly, f is computable in polynomial time. (It is easy to count the number of vertices and edges in G. There are just k vertices and fewer than k2 of edges in C, and k must be no larger than the size of G, so you can write down graph C in polynomial time.) Also, G has a clique of size k if and only if G contains a subgraph isomorphic to C. So f is a polynomial time reduction from the clique problem to the subgraph isomorphism problem.
By the way, can you show that the subgraph isomorphism problem is in NP? Be careful. The problem of testing whether two given graphs are isomorphic is not known to be solvable in polynomial time (and is conjectured not to be solvable in polynomial time).