What is the definition of a Turing recognizable set?
A set S is Turing recognizable if there exists a Turing machine program p such that S = {x | p(x) halts}.
What is the definition of an m-complete set?
A set S is m-complete if S is Turing recognizable and for every Turing recognizable set X, X m-reduces to S.
Let A = {p | p accepts input 0} and B = {p | p accepts input 1}. Show that A m-reduces to B.
For a given program p let f(p) be the program q written as follows.
q(x):
1. Run p(0).
2. If p(0) halts and accepts, then answer yes, else answer no.
Notice that q accepts in 1 if and only if p accepts 0. Since f
is clearly computable (it just has to write down program q, building
program p into it) f is an m-reduction from A to B.
Show that the language A = {p | p accepts input 0} is recursively enumerable.
Write program R as follows.
R(p):
1. Run p(0).
2. If p halted and accepted input 0 then stop else loop forever.
Notice that R(p) halts if and only if p is in A. So A is
Turing recognizable. But that means A is recursively enumerable too,
since the terms Turing recognizable and recursively enumerable
have the same meaning.
Show that the language A = {p | p is a program and p(0) = 1} is m-complete.
We know that A is Turing-recognizable, by the argument of the preceding question. So it suffices to show that the halting problem m-reduces to A. Let f(p,x) produce program q, written as follows.
q(y):
1. Run p(x).
2. Answer 1.
Notice that q(0) answers 1 if and only if p(x) halts. (If p(x) does
not halt then q(0) gets stuck in step 1 and never gives an answer.)
So q is in A if and only if the pair (p,x) is in H. Since f is
clearly computable, it is an m-reduction from H to A.
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 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-)
Yes, this is satisfiable. For example, choose x = F, y = F, z = T.
What famous conjecture needs to be proved in order to conclude that there is no polynomial time algorithm to solve the vertex cover problem?
You would need to prove that P is different from NP, since the vertex cover problem has a polynomial time algorithm if and only if P = NP.
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.)
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.