4
$\begingroup$

I was wondering if the following property holds true:

$$\forall A, B \subseteq \Sigma^* : A \leq_m B \lor B \leq_m A$$

And the same for Turing reductions

$$\forall A, B \subseteq \Sigma^* : A \leq_T B \lor B \leq_T A$$

$\endgroup$
5
  • 3
    $\begingroup$ What are your thoughts? Have you tried to search for counterexamples? Are you referring only to polynomial-time reductions, or reductions that can use an arbitrary amount of running time? See en.wikipedia.org/wiki/Turing_degree $\endgroup$
    – D.W.
    Mar 1, 2017 at 7:12
  • 2
    $\begingroup$ For $\leq_m$, try the halting problem and its complement. $\endgroup$
    – chi
    Mar 1, 2017 at 8:35
  • 2
    $\begingroup$ Empty set and its complement work too. $\endgroup$ Mar 1, 2017 at 12:28
  • $\begingroup$ @D.W. Reductions can use an arbitrary amount of time (they need to halt on all inputs though). chi and AndreaAsperti have shown that this property is not true for $\leq_m$ reductions. Also, in the case of $\leq_T$ reductions, I think that both $A$ and $B$ need to be undecidable because if one of them is not, then it trivially reduces to the other. Also, if both languages are in the Arithmetical Hierarchy, then also one will reduce to the other (by definition). So, are there languages outside the hierarchy? (I am the asker, asked as a guest because I wasn't logged in). $\endgroup$ Mar 1, 2017 at 13:45
  • 1
    $\begingroup$ It's not true that any two languages in the arithmetical hierarchy are comparable. This is only true for languages complete for levels of the arithmetical hierarchy. $\endgroup$ Mar 1, 2017 at 15:25

1 Answer 1

5
$\begingroup$

If $A \not \preceq B$ and $B \not \preceq A$ then we say that $A,B$ are incomparable with respect to the order $\preceq$.

As mentioned in the comments, the halting problem and its complement are incomparable with respect to many-one reductions; indeed, one of the reasons behind considering many-one reductions is that they make such distinctions possible.

One can also construct sets $A,B$ which are incomparable with respect to Turing reductions. These are known as incomparable Turing degrees. One way to do it is using diagonalization, as we explain below.

It will be somewhat less confusing to construct Boolean functions $\alpha,\beta$ instead of sets $A,B$. The construction will proceed in infinitely many steps. At step $i$ we will have finite partial functions $\alpha_i,\beta_i$, which extend the functions $\alpha_{i-1},\beta_{i-1}$ from the previous step. Initially, $\alpha_0 = \beta_0$.

At step $2i$, we make sure that the $i$th program cannot compute $\alpha$ given $\beta$. We start by picking the minimal input $x$ not in the support of $\alpha_i$. For each complete function $\beta'$ extending $\beta_i$, we run program $i$ on input $x$ with $\beta'$ as oracle. If none of these runs ever terminates, we set $\alpha_{i+1}(x)$ arbitrarily, and continue to the next step. Otherwise, suppose that program $i$ terminates on input $x$ with $\beta'$ as oracle. Since the program terminates, it only accesses the oracle at a finite number of places. We extend $\beta_i$ to $\beta_{i+1}$ so that it agrees with $\beta'$ on this finite number of places. Finally, we set $\alpha_{i+1}(x)$ to disagree with the output of program $i$ on input $x$ and oracle $\beta'$.

At step $2i+1$ we make sure that the $i$th program cannot compute $\beta$ given $\alpha$, in the same way. Our construction ensures that $\alpha = \bigcup_i \alpha_i$ and $\beta = \bigcup_i \beta_i$ are total functions that correspond to incomparable Turing degrees.

$\endgroup$
7
  • $\begingroup$ What does extending a boolean function mean? Also, what does, "x not in the support of a_i" mean? Also, "if none of these runs ever terminates", how do we check this condition? If it never terminates, then we won't be able to construct the function. I don't know much about boolean functions so I don't understand most of the answer. $\endgroup$ Mar 1, 2017 at 14:11
  • 1
    $\begingroup$ The support of $\alpha_i$ is the set of inputs on which $\alpha_i$ is defined. To extend the functions means to define it on more inputs, while keeping its value of the inputs on which it is already defined. Finally, there is no need to check this condition in a computable way. It's a proof, not an algorithm. $\endgroup$ Mar 1, 2017 at 14:13
  • $\begingroup$ Oh ok. Also, you say that $\alpha$ and $\beta$ are computable functions. But aren't any two computable functions turing reducible to each other? The reduction Turing machine can simply compute the answer to the function without using the oracle. $\endgroup$ Mar 1, 2017 at 14:23
  • $\begingroup$ They better not be! Where do I state that? $\endgroup$ Mar 1, 2017 at 14:25
  • 3
    $\begingroup$ A total function is a function defined on every input. This terminology has nothing to do with computability. $\endgroup$ Mar 1, 2017 at 14:27

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.