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.
$\begingroup$
$\endgroup$
1
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