Complexity: Reduction

The following pertains to Complexity questions in Spring 1999, Spring 20003, Spring 2007, Fall 2010.

Definition: A "Reduction" is a Turing transducer (a TM that computes an output, not just a YES or NO) that accepts an instance of problem A as input and computes an instance of problem B as an output. It converts one problem to another.

So A <= B means that a transducer exists that does this conversion.

Specifically, A <=p B means that a transducer does the work in polynomial time, that is, O(nk).

Another way to view A <= B (whether polynomially or not) is that B cannot be easier than A. That is, B is at least as difficult as a problem in A.

This leads to the following results.

  1. Suppose you know nothing about A, but A <= B and B is decidable. This means A is decidable. We do not know A is in P, NP, etc. just that it is decidable.
  2. If A <=p B, and B is in P, then A is in P (polynomial steps to convert A to B plus polynomial steps to decide B).
  3. But consider the converse. Suppose A <=p B, and A is in P. We know tht B is at least as difficult as A. So B might be in P, or anywhere beyond. We cannot really say anything.
  4. If A <=p B, and B is in NP, then A is in NP (polynomial steps to convert A to B plus nondetertministically solve B).
  5. The alternative proof that A is in NP: construct an algorithm to nondetermnistically guess solutions to A, and verify YES polynomially.
  6. If B is in NP, and all NP-Complete problems R <=p B, then B is NP-Complete by definition.
  7. If A <=p B, and A is NP-Complete, then B is NP-Hard by definition.
  8. If A <=p B, A is NP-Complete, and B is in NP, then B is NP-Complete (B is in NP, and all NP-complete problems now reduce to B via A).
  9. If A <=p B, and B is NP-Complete, then A is in NP, since B is in NP. We cannot say that A is NP-Complete because we do not know if all NP-Complete problems R reduce to A.

Definition: A is "co-acceptable" means that the complement of A is acceptable.

If A <= B, and B is co-acceptable, then we can only say A is co-acceptable, not that A is decidable.
If A is both co-acceptable and acceptable, then A is by definition decidable.

Consider complexity theory vs. decidability theory:

If A <=p B and B is in P, but someone claims that A is in EXP, then A could be reduced to B in polynomial steps and then B could be solved in polynomial steps. So A was really in P from the start (of course, it can still be said that A is in EXP). When considering complexity classes, the reductions must be polynomial to have relevance. It is known that problems in P, NP, EXP, etc. are decidable.

As for decidability, if A were a member of EXP, then A is decidable. If B in P, then B is decidable. If A can reduce to B (polynomial of otherwise), then A is not more difficult than B.