7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ why do you want $T$ to be total ? $\endgroup$
    – Denis
    Sep 30 '14 at 10:59
  • $\begingroup$ 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. $\endgroup$
    – DRMacIver
    Sep 30 '14 at 11:03
7
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ I see that Denis posted a similar answer while I was typing this. However, my construction actually gives a total order, as required. $\endgroup$ Sep 30 '14 at 11:27
3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – DRMacIver
    Sep 30 '14 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.