CS154 Assignment #7 and CS154N Asssignment #3
Practice Homework  Not To Be Handed In

The clique problem  does a given graph G have a clique
(set of nodes with all possible edges between any two of them present)
of size k  is NPcomplete.
Prove this fact by reducing the problem IS (independent set, as discussed in
Section 10.4.2) to the clique problem.

Suppose there are polynomialtime reductions from problem A
to problem B, from B to C, and from D to
C.
Let S be the subset of {A,B,C,D} that have polynomialtime
algorithms.
What are all the possible subsets S could be?

(This is easy; don't look for anything deep.)
Let Q be the property of RE languages L: ``L is in NP
but not in P.''
Prove that Q is decidable if and only if P=NP.
Remember to prove both directions of the ``if and only if.''

SAT100 is the satisfiability problem restricted to expressions with
at most 100 variables.
What can you say about the NPcompleteness of SAT100?

Prove that if the complement of even one NPcomplete problem is in NP,
then NP = coNP (and therefore the complement of every NPcomplete problem
is in NP).