Why can't I use a polynomial-time reduction for proving P-completeness?

206 Views Asked by At

According to https://en.wikipedia.org/wiki/P-complete, "a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction. [...] Generically, reductions weaker than polynomial-time reductions are used, since all languages in P are P-Complete under polynomial-time reductions."

I'm not sure I can understand it. May you elaborate on why can't I use a polynomial-time reduction for proving P-completeness?

1

There are 1 best solutions below

0
On BEST ANSWER

Intuitively, if you’re reducing one problem to another, the idea should be that you’re essentially just transforming the input rather than doing the actual computational work of solving the problem. If your reduction is allowed to do “too much” work, then the reduction itself might be able to do something like this:

  1. Solve the original problem.
  2. If the answer is “yes,” output a yes instance of the target problem.
  3. Otherwise, output a no instance of the target problem.

In the case of proving P-completeness, if you allow for polynomial-time reductions, the resources afforded to the reduction are the same as the resources you’re allowed to use to solve the target problem. That means that you could use the above strategy to reduce one problem to another, where the reduction itself does all the work.

On the other hand, if your reduction is afforded something we suspect is “fewer” computational resources than what you’re allowed to use after performing the reduction, then the reduction step (probably) doesn’t have enough computational power to actually solve the relevant problem. Instead, it just has enough power to transform the input.

(This is the same reason, for example, we don’t use mapping reducibility when talking about NP-hardness. If the reductions we used there had the ability to do arbitrary calculations, they’d have more computational power than a polynomial-time nondeterministic TM).