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