patternMinor
Do reductions form a total binary relation?
Viewed 0 times
totalbinaryreductionsformrelation
Problem
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$$
$$\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$$
Solution
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.
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.
Context
StackExchange Computer Science Q#71006, answer score: 5
Revisions (0)
No revisions yet.