<p>I have an example where $T$ is not total, and is only a pre-order. On the other hand, $S$ is in $\mathbf P$ and $T$ is undecidable, so it is even worse than being not polynomial.</p>

<p>The pre-order $S$ is on encodings $\langle M,x\rangle$, where $M$ is the encoding of a Turing Machine, and $x$ is a number of steps in unary.</p>

<p>We define $(\langle M,x\rangle, \langle N,y\rangle)\in S$ when if $M$ stops in less than $x$ steps, then $N$ stops in less than $y+1$ steps. Notice that we can have $(i,j)\in S$ and $(j,i)\in S$ without $i=j$ (for instance if both machines do not terminate). $S$ is computable polynomially since it suffices to simulate both machines for a linear number of steps (in the size of the input).</p>

<p>Now, let's look at the transitive closure $T$ of $S$. Take $i=\langle M,x\rangle$ such that $M$ stops in less than $x$ steps. Then $(i,\langle N,0\rangle)\in T$ iff $N$ stops (in any number of steps), which is undecidable.</p>

<p>Maybe from this we could derive $S$ and $T$ fitting your requirements, but it seems to me the constraints are artificial, could you justify them?</p>

CC BY-SA 3.0
2014-09-30T11:18:25.330Z
2014-09-30T11:47:37.030Z
2014-09-30T11:47:37.030Z
Denis
<p>Leaving the current answer accepted because it's closer to the original question than this, but I've realised the following nice class of almost example where as Denis suggested we drop the restriction that the order be total, so I thought I'd share (not suggesting this is a "better" answer, only that it was easier for me to understand and seems somehow natural so it might be of interest).</p>

<p>Consider any language L in NP. Consider (some efficient enumeration of) $\mathbb{N} \cup \mathbb{N}^2 \cup \{\mathcal{W}\}$ (where $\mathcal{W}$ is just some convenient atomic symbol). Let $f : \mathbb{N}^2 \to \{0, 1\}$ be some polynomial time function such that $i \in L$ iff for some $j$, $f(i, j) = 1$. </p>

<p>Define $T$ as the union of:</p>

<ul>
<li>$A = \{ (i, \mathcal{W}) : i \in L \}$</li>
<li>$B = \{ (i, (i, j)) : i, j \in \mathbb{N} \}$</li>
<li>$C = \{ ((i, j), \mathcal{W}) :  i, j \in \mathbb{N}, f(i, j) = 1\}$</li>
</ul>

<p>Then deciding if $(i, \mathcal{W}) \in T$ is equivalent to whether $i \in L$, so the decision problem for $T$ is NP-hard. </p>

<p>But let $S = B \cup C$. Deciding whether $x \in B$ is trivially in P, and deciding if $((i, j), \mathcal{W}) \in C$ is equivalent to computing $f$, which is in P by hypothesis, so deciding if $x \in S$ is in P.</p>

<p>But $(i, \mathcal{W}) \in T$ iff there is some $j$ such that $((i, j), \mathcal{W}) \in C$, so $T$ is the one-step transitive closure of $S$.</p>

CC BY-SA 3.0
2014-09-30T13:09:46.623Z
I guess you can do a similar trick except instead encoding a turing machine in $\mathbb{N}$, let $(i, j) \preceq \mathcal{W}$ if turing machine $i$ halts by step $j$ and then you've got something similar to Denis's solution in that the transitive closure solves the halting problem even though $S$ is in P.
DRMacIver
CC BY-SA 3.0
2014-09-30T12:55:05.663Z
2014-09-30T12:55:05.663Z
DRMacIver
<p>Note that the conditions imply that $T$ is recursive. The construction below shows that apart from that, its complexity can be arbitrarily large.</p>

<p>Let $L\subseteq\mathbb N$ be an arbitrary recursive language, and $f\colon\mathbb N\to\mathbb N$ a function such that $x\in L$ is decidable in time $|f(x)|$, and the subgraph $\{(x,y):y&lt;f(x)\}$ is polynomial-time decidable. (Here $x,y$ are assumed to be written in binary as usual.) Let $(x,y,i)$ be an efficient bijective enumeration of triples where $x,y\in\mathbb N$, and $i=0,1$. Let $S$ consist of the following pairs of these triples:</p>

<ul>
<li><p>$((x,y,i),(x',y',i'))$ for $x&lt;x'$.</p></li>
<li><p>$((x,y,i),(x,y',i))$ for $y&lt;y'&lt;f(x)$.</p></li>
<li><p>$((x,f(x),0),(x,0,1))$ and $((x,f(x),1),(x,f(x)+1,0))$ if $x\in L$.</p></li>
<li><p>$((x,f(x),1),(x,0,0))$ and $((x,f(x),0),(x,f(x)+1,0))$ if $x\notin L$.</p></li>
<li><p>$((x,y,i),(x,y',i'))$ if $f(x)&lt;y$ and $2y+i&lt;2y'+i'$.</p></li>
</ul>

<p>The properties of $f$ ensure that $S$ is polynomial-time decidable, and it is easy to see that its transitive reflexive closure is a total order $T$. However, $T$ is as hard to compute as $L$, since $((x,0,0),(x,0,1))\in T$ iff $x\in L$. (Conversely, $T$ is easily seen to be reducible to $L$.)</p>

CC BY-SA 3.0
2014-09-30T11:27:53.900Z
I see that Denis posted a similar answer while I was typing this. However, my construction actually gives a total order, as required.
Emil Jeřábek
CC BY-SA 3.0
2014-09-30T11:26:12.857Z
2014-09-30T11:26:12.857Z
Emil Jeřábek
<p>I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one.</p>

<p>Consider $T \subseteq \mathbb{N}^2$, a set representing a total order. That is we have some total order $\preceq$ such that $i \preceq j$ iff $(i, j) \in T$. </p>

<p>Does there exist $T$ and a subset $S \subseteq T$ such that:</p>

<ol>
<li>The decision problem $(i, j) \in T$ is "probably not in P". e.g. is NP-hard or is provably not in P.</li>
<li>The decision problem $(i, j) \in S$ is in P</li>
<li>$T$ is the transitive closure of $S$ (i.e. the smallest set $M$ containing $S$ such that if $(i, j), (j, k) \in M$ then $(i, k) \in M$)</li>
</ol>

<p>Note that if e.g. there's some polynomial $p$ such that for all $(i, j) \in S$ there exists some $k \leq p(i, j)$ with $(i, k), (k, j) \in T$ then the decision problem for $S$ is necessarily in NP (because you can provide such a k and verifying that it works is polynomial in $i, j$), but I suspect there are examples which don't satisfy this.</p>

CC BY-SA 3.0
2014-09-30T10:59:13.543Z
why do you want $T$ to be total ?
Denis
CC BY-SA 3.0
2014-09-30T11:03:19.247Z
I'd be interested in examples where it weren't too, but the motivation for this comes from thinking about decision theory and the VNM axioms, and I was thinking about how transitivity could be the "hard part" of insisting on consistency because in some cases a proof of transitivity looked like trying to solve an NP-hard problem, so it would be nice to have an example where that was all that was hard about it.
DRMacIver
<time-complexity><total-ordering>
Total orders which are the transitive closure of a set in P
DRMacIver
# Total orders which are the transitive closure of a set in P

(Asked by: username_0 on 2014-09-30)

I am wondering if there is an example of the following form. It seems highly plausible that there should be but I am struggling to come up with one.

Consider $T \subseteq \mathbb{N}^2$, a set representing a total order. That is we have some total order $\preceq$ such that $i \preceq j$ iff $(i, j) \in T$.

Does there exist $T$ and a subset $S \subseteq T$ such that:

1. The decision problem $(i, j) \in T$ is "probably not in P". e.g. is NP-hard or is provably not in P.
2. The decision problem $(i, j) \in S$ is in P
3. $T$ is the transitive closure of $S$ (i.e. the smallest set $M$ containing $S$ such that if $(i, j), (j, k) \in M$ then $(i, k) \in M$)

Note that if e.g. there's some polynomial $p$ such that for all $(i, j) \in S$ there exists some $k \leq p(i, j)$ with $(i, k), (k, j) \in T$ then the decision problem for $S$ is necessarily in NP (because you can provide such a k and verifying that it works is polynomial in $i, j$), but I suspect there are examples which don't satisfy this.

**Tags:** time-complexity, total-ordering

> **Comments:**
> **username_1**: why do you want $T$ to be total ?  
> **username_0**: I'd be interested in examples where it weren't too, but the motivation for this comes from thinking about decision theory and the VNM axioms, and I was thinking about how transitivity could be the "hard part" of insisting on consistency because in some cases a proof of transitivity looked like trying to solve an NP-hard problem, so it would be nice to have an example where that was all that was hard about it.  

---

## 3 answers

### Answer by username_2 on 2014-09-30. Score: 7 | Accepted answer

Note that the conditions imply that $T$ is recursive. The construction below shows that apart from that, its complexity can be arbitrarily large.

Let $L\subseteq\mathbb N$ be an arbitrary recursive language, and $f\colon\mathbb N\to\mathbb N$ a function such that $x\in L$ is decidable in time $|f(x)|$, and the subgraph $\{(x,y):y

* $((x,y,i),(x',y',i'))$ for $x
* $((x,y,i),(x,y',i))$ for $y
* $((x,f(x),0),(x,0,1))$ and $((x,f(x),1),(x,f(x)+1,0))$ if $x\in L$.
* $((x,f(x),1),(x,0,0))$ and $((x,f(x),0),(x,f(x)+1,0))$ if $x\notin L$.
* $((x,y,i),(x,y',i'))$ if $f(x)

The properties of $f$ ensure that $S$ is polynomial-time decidable, and it is easy to see that its transitive reflexive closure is a total order $T$. However, $T$ is as hard to compute as $L$, since $((x,0,0),(x,0,1))\in T$ iff $x\in L$. (Conversely, $T$ is easily seen to be reducible to $L$.)

> **Comments:**
> **username_2**: I see that username_1 posted a similar answer while I was typing this. However, my construction actually gives a total order, as required.  

---

### Answer by username_1 on 2014-09-30. Score: 3

I have an example where $T$ is not total, and is only a pre-order. On the other hand, $S$ is in $\mathbf P$ and $T$ is undecidable, so it is even worse than being not polynomial.

The pre-order $S$ is on encodings $\langle M,x\rangle$, where $M$ is the encoding of a Turing Machine, and $x$ is a number of steps in unary.

We define $(\langle M,x\rangle, \langle N,y\rangle)\in S$ when if $M$ stops in less than $x$ steps, then $N$ stops in less than $y+1$ steps. Notice that we can have $(i,j)\in S$ and $(j,i)\in S$ without $i=j$ (for instance if both machines do not terminate). $S$ is computable polynomially since it suffices to simulate both machines for a linear number of steps (in the size of the input).

Now, let's look at the transitive closure $T$ of $S$. Take $i=\langle M,x\rangle$ such that $M$ stops in less than $x$ steps. Then $(i,\langle N,0\rangle)\in T$ iff $N$ stops (in any number of steps), which is undecidable.

Maybe from this we could derive $S$ and $T$ fitting your requirements, but it seems to me the constraints are artificial, could you justify them?


---

### Answer by username_0 on 2014-09-30. Score: 2

Leaving the current answer accepted because it's closer to the original question than this, but I've realised the following nice class of almost example where as username_1 suggested we drop the restriction that the order be total, so I thought I'd share (not suggesting this is a "better" answer, only that it was easier for me to understand and seems somehow natural so it might be of interest).

Consider any language L in NP. Consider (some efficient enumeration of) $\mathbb{N} \cup \mathbb{N}^2 \cup \{\mathcal{W}\}$ (where $\mathcal{W}$ is just some convenient atomic symbol). Let $f : \mathbb{N}^2 \to \{0, 1\}$ be some polynomial time function such that $i \in L$ iff for some $j$, $f(i, j) = 1$.

Define $T$ as the union of:

* $A = \{ (i, \mathcal{W}) : i \in L \}$
* $B = \{ (i, (i, j)) : i, j \in \mathbb{N} \}$
* $C = \{ ((i, j), \mathcal{W}) : i, j \in \mathbb{N}, f(i, j) = 1\}$

Then deciding if $(i, \mathcal{W}) \in T$ is equivalent to whether $i \in L$, so the decision problem for $T$ is NP-hard.

But let $S = B \cup C$. Deciding whether $x \in B$ is trivially in P, and deciding if $((i, j), \mathcal{W}) \in C$ is equivalent to computing $f$, which is in P by hypothesis, so deciding if $x \in S$ is in P.

But $(i, \mathcal{W}) \in T$ iff there is some $j$ such that $((i, j), \mathcal{W}) \in C$, so $T$ is the one-step transitive closure of $S$.

> **Comments:**
> **username_0**: I guess you can do a similar trick except instead encoding a turing machine in $\mathbb{N}$, let $(i, j) \preceq \mathcal{W}$ if turing machine $i$ halts by step $j$ and then you've got something similar to username_1's solution in that the transitive closure solves the halting problem even though $S$ is in P.  

---

