# Natural NP-complete problems with “large” witnesses

The question on cstheory "What is NP restricted to linear size witnesses?" asks about the class NP restricted to linear size $O(n)$ witnesses, but

Are there natural NP-complete problems in which (yes) instances of size $n$ require witnesses of size greater than $n$?

Clearly we can build artificial problems like:

• $L = \{ 1^nw \mid w \text{ encodes a satisfiable formula and } |w|=n \}$
• $L = \{ \varphi \mid \varphi \text{ is SAT formula with more than } |\varphi|^2 \text{ satisfying assignments}\}$

After a quick look at G&J, every natural NPC problem seems to have witnesses (strictly) smaller than $n$.

Is there a "reason/explanation" for it ?

• Many problems have witness size $\Theta(n \log n)$, like graph isomorphism and Hamiltonian path. Did you want to exclude polylog factors, or does that count as an answer? – Joshua Grochow Oct 26 '14 at 20:32
• Actually, the witness size for Graph Isomorphism and Hamiltonian Path could be seen as sublinear in the input (given that the input is the $n \times n$ adjacency matrix of the graph). – Ryan Williams Oct 26 '14 at 20:54
• Oh, right...d'oh. – Joshua Grochow Oct 27 '14 at 3:26
• @MarzioDeBiasi I think your observation of small witnesses should be used to define natural NP-complete problem. – Mohammad Al-Turkistany Oct 29 '14 at 23:14
• @MarzioDeBiasi - I agree that a list of the satisfying assignments is enough, but can you prove that there is no shorter witness for the problem? (maybe a succinct way of representing the needed assignments). – R B Oct 30 '14 at 10:58

How about the edge coloring number in a dense graph (aka Chromatic index)? You are given the adjacency matrix of an $n$ vertex graph ($n^2$ bit input), but the natural witness describing the coloring has size $n^2\log n$. Of course, there might be shorter proofs for class 1 graphs in Vizing's theorem.

• It seems a good example! Just a note: the problem is NP-complete even for cubic graphs; in that case we have that a witness of size $2|E|$ bits is enough (two bits for every edge) which is less than $n^2$ if we use the adjacency matrix representation and I suspect that it is less than the instance size whatever reasonable encoding we use for the cubic graph. – Marzio De Biasi Oct 28 '14 at 8:01

I came along some quite natural NP-complete problems that seemingly require long witnesses. The problems, parameterized by integers $C$ and $D$ are as follows:

Input: A one-tape TM $M$
Question: Is there some $n\in\mathbb{N}$, such that $M$ makes more than $Cn+D$ steps on some input of length $n$?

Sometimes the complement of the problem is easier to state: Does a given one-tape TM $M$ run in time $Cn+D$, ie. does it make at most $Cn+D$ steps on all inputs of size $n$, for all $n$?

The full result is presented here. Basically, it is shown that if we want to verify whether a one-tape TM runs in time $Cn+D$, we only need to verify this on inputs of length bounded by $q^{O(C)}$, where $q$ is the number of states of the input TM. So the witness would be the input of length $q^{O(C)}$ for which the time bound is violated. It is also shown in the reference that these problems are NP-complete for all $C\geq 2$ and $D\geq 1$.

Now if the witness is an input that violates the running time, it has to be of length $q^{\Omega(C)}$ in general. And the input is of length $O(q^2)$.

• Thanks! But, to be honest, I find more "natural" (I know it's not a formal concept) the problem: "Given a formula $\varphi$, decide if it has at least $|\varphi|^2$ satisfying assignments" :-) – Marzio De Biasi Oct 29 '14 at 7:47
• I understand :). On the other hand, the problem about $\varphi$ has the length of the witness in the question, while the problem about TMs gets the length of the witness in the proof. What is more, the length of the witness is not intentionally incorporated into the problem. – David G Oct 29 '14 at 17:18

Here is an example, which appears a natural problem.

Instance: Positive integers, $d_1,\ldots,d_n$ and $k$, all bounded from above by $n$.

Question: Does there exist a $k$-colorable graph with degree sequence $d_1,\ldots,d_n$ ?

Here the input can be described with $O(n\log n)$ bits, but the witness may require $\Omega(n^2)$ bits.

Remark: I do not have a reference that this particular problem is indeed NP-complete. But the requirement of $k$-colorability could be replaced by any other NP-complete condition; the problem will likely become NP-complete for some condition, if not for this one.

• To me, this problem has the wrong kind of structure to be NP-complete, unless P=NP. The classes of graphs defined by each degree sequence can be very large, and many of them may have $n$-colourable elements for a trivial reason. – András Salamon Oct 7 '15 at 5:57
• @AndrásSalamon Indeed, I do not know what the complexity of this problem is, or whether it can be made NP-complete by choosing an appropriate condition instead of $k$-colorability. On the other hand, I would be surprised if for every polytime checkable property $Q$ the following problem would be in P: does there exist a graph with a given degree sequence, such that it also has property $Q$? – Andras Farago Oct 7 '15 at 16:18
• I agree that it seems unlikely that degree sequence + property is always in P, but perhaps some of these are candidates for NP-intermediate status? – András Salamon Oct 7 '15 at 23:04
• @AndrásSalamon Yes, I can very well imagine that some of them has NPI status. – Andras Farago Oct 9 '15 at 14:59

Maybe this is a silly "reason/explanation", but for many NP-Complete problems, a solution is a subset of the input (knapsack, vertex cover, clique, dominating set, independent set, max cut, subset sum, ...) or a permutation of or assignment to a subset of the input (Hamiltonian path, traveling salesman, SAT, graph isomorphism, graph coloring, ...).

We could try to read more into it than that, or come up with a more fancily-stated reason, but I'm not sure whether there is anything deeper going on or not.

• I think this is a fine "first idea" indeed. Sometimes the problems can't be classified unambiguously. For instance, SAT could also be a subset problem ("choose a subset of true variables"). Or is HAMCYCLE a permutation problem on vertices, or a subset problem on edges? (BTW, maybe the "assignment problems" could really be "partition problems", think of say 3-coloring). – Juho Oct 27 '14 at 7:42

As for your first question, Allender states (in Amplifying Lower Bounds by Means of Self-Reducibility) that no natural NP-complete problem is known to lie outside of NTIME(n). This means that all known natural NP-complete sets have linear size witnesses.

• Note that the length of the longest accepting path in nondeterministic Turing machine corresponds to the size of the witness. – Mohammad Al-Turkistany Oct 2 '15 at 21:22

Consider the following variant of the MAXCLIQUE problem.

Instance: A circuit $C$ with $2n$ input bits, and of polynomially bounded size in $n$. This circuit implicitly determines a graph on $2^n$ vertices, such that each vertex is identified with an $n$-bit string, and two vertices are connected with an edge if the $2n$-bit string that is obtained by concatenating the two vertex IDs, is accepted by $C$. Let $G(C)$ denote this graph. Note that it has exponentially many vertices in $n$, but is still determined by the polynomial size description of $C$.

Question: Does $G(C)$ contain a clique of size $n^k$, where $k$ is a fixed constant?

Notes:

1. The problem is NP-complete. The containment in $NP$ is obvious. Completeness can be proved by observing that if the circuit accepts only vertex pairs in which each ID is at most $N=2n^k$, then $G(C)$ can be an arbitrary $N$-vertex graph plus many isolated vertices. (Any such $N$-vertex graph can be encoded in $C$, since $C$ is allowed to have polynomial size in $n$, and so also in $N$.) Then the question becomes: is there an $N/2$-sized clique in an $N$-vertex graph? This is known to be NP-complete, for general $N$. The issue that $N$ is not arbitrary, it is restricted to $N=2n^k$, can be eliminated by appropriate padding.

2. The natural witness for the original problem is the $n^k$-sized clique, which can be described by an $O(n^{k+1})$ long string (an $n$-bit string for each of the $n^k$ vertices). Note that $k$ can be a very large constant, so the witness can be much longer than linear. (Even if the input size is the description of $C$, rather than $n$, this witness can be still much longer, because $k$ can be chosen independently of $C$.)

3. The problem can be viewed as natural, since it is a variant of MAXCLIQUE.

4. When Allender wrote "no natural NP-complete problem is known to lie outside of $NTIME(n)$," (see Amplifying Lower Bounds by Means of Self-Reducibility, Section 7), he may have had a narrower concept of naturalness in mind. For example, natural could be narrowed to something that people really want to solve on the grounds of independent, practical motivations. It is not enough if the problem is not constructed via diagonalization.

• I am not sure I follow your reduction of Half-Clique to this problem, to establish completeness in NP. Given an $n$-vertex instance of Half-Clique, what circuit does it map to? – András Salamon Oct 5 '15 at 11:17
• @AndrásSalamon Let $G'$ be an $N=2n^k$-vertex graph, serving as input graph of Half-Clique. Then $C$ is the circuit that accepts any node pair $(u,v)$, if $u\leq N, \; v\leq N$ (as binary numbers), and $(u,v)\in E(G')$, otherwise $C$ rejects. (This $C$ can be implemented as a polynomial sized circuit.) Then $G(C)$ will contain $G'$ on the first $N$ nodes, plus $2^n-N$ additional isolated nodes. The graph $G(C)$ has a clique of size $n^k$ precisely when $G'$ has a half-clique. – Andras Farago Oct 5 '15 at 15:21