25
$\begingroup$

For any $n > 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is $n$-complete if, for every permutation $\mathbf{p}$ of $\{1, \ldots, n\}$, written as a sequence of pairwise distinct integers $p_1, \ldots, p_n$, the sequence $\mathbf{p}$ is a subsequence of $s$, i.e., there exist $1 \leq i_1 < i_2 < \cdots < i_n \leq |s|$ such that $s_{i_j} = p_j$ for all $1 \leq j \leq n$.

What is the complexity of the following problem? Is it in PTIME, or coNP-hard? Note that it is in coNP as you can guess a missing sequence (thanks @MarzioDeBiasi).

Input: an integer $n$, a sequence $s$ of integers in $\{1, \ldots, n\}$
Output: is $s$ $n$-complete?

The notion of $n$-complete sequence is known in combinatorics because people have investigated what is the length of the shortest $n$-complete sequences as a function of $n$ (see, e.g., this mathoverflow thread for a summary). However, I was unable to find references to the complexity of recognizing them. Note that in particular we can easily build $n$-complete sequences of length polynomial in $n$, namely, of length $n^2$, as $(1, \ldots, n)$ repeated $n$ times (any permutation $\mathbf{p}$ can be realized by choosing $p_i$ in the $i$-th block). Hence we cannot afford in general to enumerate all permutations.

$\endgroup$
  • 10
    $\begingroup$ The problem is in coNP because a missing permutation $p_1...p_n$ from the string $s$ can be checked in polynomial time. So the problem could be coNP-complete $\endgroup$ – Marzio De Biasi May 21 '15 at 20:53
  • $\begingroup$ @MarzioDeBiasi: right, this was sloppy, I edited accordingly. Thanks! $\endgroup$ – a3nm May 22 '15 at 6:06
13
$\begingroup$

I believe the problem to be coNP-complete. I have uploaded it as an arXiv preprint.

$\endgroup$
  • 2
    $\begingroup$ I have looked into this proof in detail and I confirm that it looks correct to me. Thanks a lot! $\endgroup$ – a3nm Jun 15 '15 at 9:26
  • 2
    $\begingroup$ His arXiv version is up: arxiv.org/abs/1506.05079 $\endgroup$ – Tyson Williams Jun 17 '15 at 2:30

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.