patternMinor
Number of equivalence classes in $P$
Viewed 0 times
classesnumberequivalence
Problem
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.
Solution
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$:
This runs in polynomial time since $L_1 \in \mathsf{P}$.
- 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}$.
Context
StackExchange Computer Science Q#110718, answer score: 2
Revisions (0)
No revisions yet.