Natural NP-complete problems with "large" witnesses

Question

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 ?

Answer 1

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.

See also this possibly related question

Answer 2

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

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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.