# Number of equivalence classes in $P$

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.

## 1 Answer

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

• AKA "solving the problem in the reduction" – David Richerby Jun 15 '19 at 17:45