3
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ AKA "solving the problem in the reduction" $\endgroup$ Jun 15, 2019 at 17:45
2
$\begingroup$

The existing answer is good, but doesn't tackle the empty and full languages and also leaves some doubts unspecified. I'll solve the full question.


First, let's be clear about our definitions: $L_1 \leq_p L_2$ when there is a polynomial-time mapping reduction from $L_1$ to $L_2$. That is, there is a function $f(x)$ from $L_1$ to $L_2$ so that

  1. it is a mapping reduction, i.e. $x\in L_1 \Leftrightarrow f(x)\in L_2$, and
  2. $f(x)$ is computable in $O(p(|x|))$, with $p$ some polynomial.

Polynomial equivalence $L_1 \sim_p L_2$ holds when $L_1 \leq_p L_2$ and $L_2\leq_p L_1$.

$P$ is the class of languages where each word $x$ can be decided to be in the language within $O(p(|x|))$, where $p$ is a polynomial once again.


Consider two languages $L_1$ and $L_2$ in $P\setminus\{\emptyset,\Sigma^*\}$. We have a budget of $O(p(|x|))$ time for an $f$ to map every word in $L_1$ to a word in $L_2$, and words out of $L_1$ to a word out of $L_2$. We perform the reduction as follows for a given $x$. (This is an extension of the existing answer.)

  1. Decide whether $x\in L_1$. This takes a polynomial amount of time in $|x|$, so our budget is not exceeded.
  2. Find a string $a\in L_2$ and a string $b\notin L_2$.
    • Wait, but how? What if it takes a long time to find those strings? Yes, that's possible. But it doesn't exceed our budget! Why? Because the time needed to search for a fitting $a$ and $b$ -- for example by randomly checking strings -- is independent of $|x|$. It is $O(1)$ from the perspective of the size of our input -- so are the checks by the way, since they are polynomial in $|a|$ and $|b|$ and independent of $|x|$ -- and hence this is also a polynomial-time step!
  3. If $x\in L_1$ was true, set $f(x)=a$, else $f(x)=b$.

We never exceeded our polynomial budget, and we successfully found a mapping reduction, so $L_1 \leq_p L_2$. You can swap around $L_1$ and $L_2$ and hence find $L_1 \sim_p L_2$.


Why are $\emptyset$ and $\Sigma^*$ different (both are decidable in $O(1)$ and hence they both live in $P$ too)? That's easy: if you use $\emptyset$ as $L_2$, then step 2 can't find an $a$. Thus, for all languages $L_1\in P\setminus\{\emptyset,\Sigma^*\}$, we have $L_1 \not\leq_p L_2$. But there is one $L_1$ language that can cope with the lack of $a$ in $L_2$: that's $\emptyset$ itself, because it never needs an $a$ since it rejects all strings! It's also clear that $\Sigma^*$ clearly cannot be reduced to $\emptyset$, because it accepts all strings and hence definitely needs an $a$ in $\emptyset$, so $\emptyset \not\sim_p \Sigma^*$. So, $\emptyset$ is an equivalence class by itself.

The same argument holds for $\Sigma^*$, but for finding a $b$ instead of an $a$. It is also an equivalence class by itself.


Conclusion: the equivalence relation $\sim_p$ partitions $P$ into exactly 3 equivalence classes: $\{\emptyset\}, \{\Sigma^*\}, P\setminus \{\emptyset,\Sigma^*\}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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