Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?

  • $\begingroup$ Exptime complete problems take exponential time, so they cannot be reduced to problems in P. $\endgroup$ Apr 20 '20 at 11:33
  • $\begingroup$ @AlbertHendriks but does there exist some problem that can't be reduced to by any problem whether in P, NP, NP-complete, NP-hard? $\endgroup$
    – Andy
    Apr 20 '20 at 11:35
  • 1
    $\begingroup$ A problem can always be reduced to by itself, so I suppose no. $\endgroup$ Apr 20 '20 at 11:42
  • $\begingroup$ @AlbertHendriks makes sense, thank you!! Do you know if there exist a language A such that every language B reduces to A? $\endgroup$
    – Andy
    Apr 20 '20 at 11:48
  • $\begingroup$ I can imagine that every language reduces to the halting problem. $\endgroup$ Apr 20 '20 at 13:26

As stated in the comments, every problem is reducible to itself (under any notion of reduction - polynomial-time many-one reduction, polynomial-time Turing reduction, ...).

It's worth noting that when thinking about many-one reductions there are two important "edge cases" to consider:

  • No nonempty set is many-one reducible to $\emptyset$.

  • No set other than $\mathbb{N}$ is many-one reducible to $\mathbb{N}$.

I'll prove the first, since the second is identical. Suppose $A\not=\emptyset$, and pick $a\in A$. Fixing any function $f$ whatsoever, we have $a\in A$ but $f(a)\not\in \emptyset$, so $f$ is not a many-one reduction of $A$ to $\emptyset$. This doesn't impact your main question, but it does illustrate a subtlety of many-one reductions. (Note that this doesn't apply to more complex reductions like Turing or truth-table: with respect to such notions, all computable sets are reducible to each other.)

You also ask in the comments whether there is some $X$ such that every set is reducible to $X$. The answer is no, regardless of what reducibility we use:

  • One natural example, applicable to all the usual reducibility notions in complexity theory, is provided by the Turing jump: every language $A$ has a "halting problem analogue," $A'$. The usual proof that the halting problem is not computable relativizes to show that $A'$ is not Turing-reducible to $A$, and a very simple argument shows additionally that $A$ is $1$-reducible to $A'$ - even logtime-$1$-reducible, under a mild assumption on the enumeration of oracle Turing machines we use. So in a very strong sense every set is strictly less complicated than its jump.

    • Incidentally the "complexity interval" between a set and its jump is always quite rich: the jump is very much not a successor operation. So in some sense using the jump here is massive overkill. However, there's no "natural" way so far as we know to build such "intermediate" sets (and this is why the halting problem is the canonical example of a non-computable set!). Indeed it's broadly conjectured that there are no "natural" sets $A,B$ such that $B$ is strictly between $A$ and $A'$ in terms of Turing reducibility, and we know some technical results along these lines. So introducing the Turing jump here is kind of unavoidable if we don't want to do weird stuff.
  • More coarsely, basically all of the reductions we consider in the context of computability theory have the property that they're indexed by natural numbers: for any $A$, there are only countably many $B$ which are reducible to $A$ according to that notion. Now apply Cantor.

    • This applies even to very strong reducibilities like hyperarithmetic reducibility (which in particular is so strong that the halting problem and the Turing jump in general is totally irrelevant). To break out of this situation we need to either look at "ambiguous" reducibilities like generic or coarse reductions or set-theoretic reducibilities like relative constructibility which are consistently fairly trivial. But the former are still subject to the "no-top-element" issue in a coarse manner by only slightly messier arguments, and the latter are generally only studied under additional assumptions which make them nontrivial (and in particular, lacking a top element).

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.