Total orders which are the transitive closure of a set in P

Question

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.

Answer 1

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<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<x'$.

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

Answer 2

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 3

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

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