What is the definition of a Turing recognizable set?
What is the definition of an m-complete set?
Let A = {p | p accepts input 0} and B = {p | p accepts input 1}. Show that A m-reduces to B.
Show that the language A = {p | p accepts input 0} is recursively enumerable.
Show that the language A = {p | p is a program and p(0) = 1} is m-complete.
What is the definition of an NP-complete problem?
Is the following boolean formula satisfiable? I will use ^ for and, | for or and x- for the negation of x.
(x | y | z) ^ (x- | y-) ^ (x- | z-) ^ (y- | z-)
What famous conjecture needs to be proved in order to conclude that there is no polynomial time algorithm to solve the vertex cover problem?
Describe the error in the following fallacious "proof" that P is different from NP.
A propositional 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.)