complexity - Non Polynomial reduction

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

2 Answers

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

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.