<p>I believe the problem to be coNP-complete.
I have uploaded it as an arXiv <a href="http://arxiv.org/abs/1506.05079" rel="nofollow">preprint</a>.</p>

CC BY-SA 3.0
2015-06-15T09:26:08.047Z
I have looked into this proof in detail and I confirm that it looks correct to me. Thanks a lot!
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-06-17T02:30:04.007Z
His arXiv version is up: http://arxiv.org/abs/1506.05079
Tyson Williams
CC BY-SA 3.0
2015-06-10T01:04:40.853Z
2015-06-18T09:43:39.410Z
2015-06-18T09:43:39.410Z
Przemysław Uznański
<p>For any $n &gt; 0$, I say that a sequence $s$ of integers in $\{1, \ldots, n\}$ is <em>$n$-complete</em> 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 &lt; i_2 &lt; \cdots &lt; i_n \leq |s|$ such that $s_{i_j} = p_j$ for all $1 \leq j \leq n$.</p>

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

<p><strong><em>Input:</em></strong> an integer $n$, a sequence $s$ of integers in $\{1, \ldots, n\}$<br>
<strong><em>Output:</em></strong> is $s$ $n$-complete?</p>

<p>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., <a href="https://mathoverflow.net/a/165321/16035">this mathoverflow thread</a> 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.</p>

CC BY-SA 3.0
2015-05-21T20:53:13.070Z
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
Marzio De Biasi
CC BY-SA 3.0
2015-05-22T06:06:11.327Z
@MarzioDeBiasi: right, this was sloppy, I edited accordingly. Thanks!
Antoine Amarilli 'a3nm'
<cc.complexity-theory><co.combinatorics><np-hardness><permutations>
Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences
Antoine Amarilli 'a3nm'
# Recognizing sequences with all permutations of $\{1, \ldots, n\}$ as subsequences

(Asked by: username_0 on 2015-05-21)

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](https://mathoverflow.net/a/165321/16035) 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.

**Tags:** cc.complexity-theory, co.combinatorics, np-hardness, permutations
> **Comments:**
> **username_1**: 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  
> **username_0**: @MarzioDeBiasi: right, this was sloppy, I edited accordingly. Thanks!  

---

## 1 answers

### Answer by username_2 on 2015-06-10. Score: 13 | Accepted answer

I believe the problem to be coNP-complete.
I have uploaded it as an arXiv [preprint](http://arxiv.org/abs/1506.05079).

> **Comments:**
> **username_0**: I have looked into this proof in detail and I confirm that it looks correct to me. Thanks a lot!  
> **username_3**: His arXiv version is up: http://arxiv.org/abs/1506.05079  

---

