We need to establish relationships among problems, with respect to how difficult the problems are to solve.
A tool for doing that is reduction. There are several kinds of reductions.
If the right kind of reduction is chosen, then the existence of a reduction from problem A to problem B allows you to conclude that, if B is in class C, then A is also in class C.
Mapping reductions are only used to reduce one decision problem to another.
A mapping reduction from A to B is a computable function f so that, for every x,
We write A ≤m B if there exists a mapping reduction from A to B.
A polynomial-time mapping reduction is a mapping reduction that is computable in polynomial time.
We write A ≤p B if there exists a polynomial-time mapping reduction from A to B.
If A ≤m B then:
B is computable ⇒ A is computable.
A is uncomputable ⇒ B is uncomputable.
B is partially computable ⇒ A is partially computable.
A is not partially computable ⇒ B is not partially computable.
Say that reducibility relation ≤ is conservative for class C if, whenever A ≤ B is true,
Equivalently, by the law of the contrapositive,
The above results can be summarized as
Relation ≤m is conservative for the computable languages and for the partially computable languages.
If A ≤p B then:
B ∈ P ⇒ A ∈ P.
A ∉ P ⇒ B ∉ P.
B ∈ NP ⇒ A ∈ NP.
A ∉ NP ⇒ B ∉ NP.
B ∈ CoNP ⇒ A ∈ CoNP.
A ∉ CoNP ⇒ B ∉ CoNP.
B ∈ PSPACE ⇒ A ∈ PSPACE.
A ∉ PSPACE ⇒ B ∉ PSPACE.
B ∈ EXPTIME ⇒ A ∈ EXPTIME.
A ∉ EXPTIME ⇒ B ∉ EXPTIME.
That is, relation ≤p is conservative for P, NP, CoNP, PSPACE and EXPTIME. (It is, of course, also conservative for the computable and partially computable problems.)
Turing reductions can be used between any kind of problems.
A Turing reduction from A to B is a program that solves A on a B-machine.
We write A ≤t B if there exists a Turing reduction from A to B.
A polynomial-time Turing reduction is a Turing reduction that runs in polynomial time.
We write A ≤pt B if there exists a Turing reduction from A to B.
Turing reductions work for deterministic classes but not for nondeterinistic or partial classes.
If A ≤t B then:
B is computable ⇒ A is computable.
A is uncomputable ⇒ B is uncomputable.
If A ≤pt B then:
B ∈ P ⇒ A ∈ P.
A ∉ P ⇒ B ∉ P.
B ∈ PSPACE ⇒ A ∈ PSPACE.
A ∉ PSPACE ⇒ B ∉ PSPACE.
Notice that Turing reductions are not conservative for nondeterministic or partial computability classes.
Some reductions are difficult to find. But some are easy. I will only ask you to do easy reductions.
An easy reduction is usually between two closely related problems.
To describe a mapping reduction, remember that a mapping reduction is a function. Say exactly what the function is. Do not leave me wondering what the function is.
After defining the function, explain why it works. Avoid mixing an explanation of why the function works with your definition of the function.
You should be prepared to carry out a simple reductions.