CSCI 4602
Fall 2000
Practice questions for quiz 4.

  1. Show that the language A = {p | p is a program and p(0) = 1} is m-complete.

  2. Show that NP is closed under the * operation.

  3. Is the following 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)

  4. What conjecture needs to be proved in order to conclude that there is no polynomial time algorithm to solve the clique problem?

  5. Exercise 7.33 of Sipser.

  6. 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.