CSCI 4602
Fall 2000
Practice questions for quiz 4.
- Show that the language A = {p | p is a program and p(0) = 1}
is m-complete.
- Show that NP is closed under the * operation.
- 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)
- What conjecture needs to be proved in order to conclude
that there is no polynomial time algorithm to solve the
clique problem?
- Exercise 7.33 of Sipser.
- 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.