Total orders which are the transitive closure of a set in 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.

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:


The decision problem $(i, j) \in T$ is "probably not in P". e.g. is NP-hard or is provably not in P.
The decision problem $(i, j) \in S$ is in P
$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.
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&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:


$((x,y,i),(x',y',i'))$ for $x&lt;x'$.
$((x,y,i),(x,y',i))$ for $y&lt;y'&lt;f(x)$.
$((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)&lt;y$ and $2y+i&lt;2y'+i'$.


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