HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Number of equivalence classes in $P$

Submitted by: @import:stackexchange-cs··
0
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$:

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