1
$\begingroup$

I have a question, does non-polynomial reduction exists for all problems? the issue is only regarding polynomial reductions?

$\endgroup$
0
1
$\begingroup$

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^*$.)

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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