I have a question, does non-polynomial reduction exists for all problems? the issue is only regarding polynomial reductions?
0
Add a comment
|
$\begingroup$
$\endgroup$
What type of reduction are you are talking about? The statement is false for Karp (many-one) reductions. Take $\mathcal L=\emptyset$. For any language $\mathcal L'\neq \emptyset$, $\mathcal L'$ cannot reduce to $\mathcal L$ by a computable algorithm $f$ because the condition $\forall x\in \Sigma^*:x\in\mathcal L' \iff f(x)\in \mathcal L$ does not hold as $f(x)\in \mathcal L$ is false but $x\in \mathcal L'$ is true for some $x$.
(The same works with $\mathcal L=\Sigma^*$ and $\mathcal L'\neq \Sigma^*$.)
$\begingroup$
$\endgroup$
You can show that it is not the case that every two languages are reducible to each other using a counting argument. Consider the class of all languages $ 2^{\Sigma^*}$. If by contradiction every two languages are reducible to each other, then every language is an $2^{\Sigma^*}$-hard language (in particular, there is a language that all languages reduce to). One can show that there are more languages than reductions. Thus, an $2^{\Sigma^*}$-hard language must have two different languages that reduce to it using the same reduction, but this is impossible.
More formally, assume by contradiction that there is an $2^{\Sigma^*}$-hard language $L$. We know that there are $2^{\aleph_0}$ languages, yet, as there are only $\aleph_0$ TMs, there are also only $\aleph_0$ reductions. Then, it follows that there are distinct languages $A$ and $B$ such that $A \leq_m L$ and $B \leq_m L$, but the reductions from $A$ and $B$ to $L$ coincide. Denote this reduction by $f$. Since $A\neq B$, there exists w.l.o.g a word $x\in A\setminus B$. Since $f$ is a reduction from $A$ to $L$, we get that $f(x) ∈ L$. But $f$ is also a reduction from $B$ to $L$, and thus we get that $f(x) \notin L$, and we reached a contradiction.
