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

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 am not sure I can understand it. May you please elaborate on why I cannot use a polynomial-time reduction for proving P-completeness?

$$P$$-completeness is defined in terms of reductions stronger than polynomial reductions. For example, the notion of log-space reductions is such a "stronger" (more restrictive) reduction.

Notice that all languages in $$P$$ are poly-reducible to each other, by definition. So defining $$P$$-completeness in terms of poly-reductions would just be useless - so indeed a different notion of reduction has to be used.

This means that showing a poly-time reduction isn't enough to prove that a language is $$P$$-complete.

• So could we say that, in general, given two classes $C_1$ and $C_2$ (with $C_2 \subset C_1$) and two problems $P_1$ and $P_2$ (with $P_2 \in C_1$-complete), if there exist a $C_2$-reduction from $P_2$ to $P_1$ then also $P_1$ is $C_1$-complete? Nov 11 '21 at 22:02
• No. It depends on what you define "being $C_1-complete$" as. You could define it in terms of $C_2$, but you could also define it in terms of some other $C_3\subset C_1$. The particular notion of $C_1$-completeness should either be explicitly said or clear from the context. For example, we can say "being $NP$-complete" without referencing the exact type of reductions - since usually we refer to polynomial reductions. But one could define a new notion of "being $NP$-complete with respect to logspace reductions", for example - we are explicit here about the reduction type. Nov 11 '21 at 22:28
• In this example, the two notions of being $NP$-complete, may result in different problems satisfying \ not satisfying the definitions. Nov 11 '21 at 22:30
• Ok, thank you! But may you also tell me why they say we need a "weaker" reduction? For what I can understand, e.g. a LogSpace-reduction would be stronger than a polytime one, since the first should imply the second. Nov 12 '21 at 9:53
• @user402843 You are quite right: you need a stronger (i.e., more restrictive) notion of reduction, rather than weaker. I fixed this terminological confusion in the Wikipedia article. Nov 12 '21 at 10:37

A more constructive demonstration: for any complexity class $$X$$ (not just for $$P$$), any problem $$P_X$$ in $$X$$ can be solved by an $$X$$-algorithm (that's the definition).

If it can be solved by an $$X$$-algorithm, it's simple to extend that algorithm to output one of two different values depending on whether the solution is yes or no - unless your complexity class is so extremely restrictive that outputting a constant string is too hard for it - which $$P$$ is not.

Now choose any other problem $$Q_Y$$ in any complexity class $$Y$$ which has at least one instance whose answer is "yes" and at least one instance whose answer is "no".

Now extend your algorithm for $$P_X$$ so that if the answer is "yes" it outputs a known (hard-coded) instance of $$Q_Y$$ whose answer is "yes" and if the answer is "no" it outputs a known (hard-coded) instance of $$Q_Y$$ whose answer is "no".

You have now constructed an algorithm which reduces $$P_X$$ to $$Q_Y$$. And this applies for every $$P_X$$ and every non-trivial $$Q_Y$$, in most complexity classes $$X$$ and all complexity classes $$Y$$. You could reduce nearly anything to nearly anything this way.

And here's an actual instance of that. Here's an $$NP$$-algorithm that reduces SAT to the problem of determining whether an integer is less than five. The reduction algorithm works like this:

1. Solve the satisfiability problem instance (in $$NP$$ time).
2. If the instance is satisfiable, output 4.
3. If the instance is unsatisfiable, output 6.

Seems silly, right? That's why we don't define it that way.