I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $\Sigma^*$ and $P - \{\phi,\Sigma^*\}$. I am unable to figure out how this is true, specifically how if $L_1,L_2 \in P, L_1 \sim_P L_2$. I think there's a simple fact/idea I am missing out on, but I don't know what it is.


Suppose that $L_1 \in \mathsf{P}$ and $L_2$ is non-trivial. Pick $y \in L_2$ and $z \notin L_2$ arbitrary. The following is a polynomial time reduction from $L_1$ to $L_2$:

  • Input: $x$.
  • Check whether $x \in L_1$.
  • If so, output $y$.
  • Otherwise, output $z$.

This runs in polynomial time since $L_1 \in \mathsf{P}$.

  • 1
    $\begingroup$ AKA "solving the problem in the reduction" $\endgroup$ – David Richerby Jun 15 '19 at 17:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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