2
$\begingroup$

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

Improve this question
$\endgroup$

2 Answers 2

Reset to default
5
$\begingroup$

$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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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? $\endgroup$
    – user402843
    Commented Nov 11, 2021 at 22:02
  • 1
    $\begingroup$ 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. $\endgroup$
    – nir shahar
    Commented Nov 11, 2021 at 22:28
  • $\begingroup$ In this example, the two notions of being $NP$-complete, may result in different problems satisfying \ not satisfying the definitions. $\endgroup$
    – nir shahar
    Commented Nov 11, 2021 at 22:30
  • 1
    $\begingroup$ 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. $\endgroup$
    – user402843
    Commented Nov 12, 2021 at 9:53
  • 2
    $\begingroup$ @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. $\endgroup$
    – Emil Jeřábek
    Commented Nov 12, 2021 at 10:37
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.