# Is the Witness Size of Membership for Every NP Language Already Known?

The question occurred to me when I get Dana Moshkovitz answer to another topic.

Let $L$ be an NP Language, and let $R_L$ be the respective NP relation. We know that there exists some polynomial $p$ such that:

$\forall x \in L, \\, \exists w \in \\{0,1\\}^{p(|x|)} \quad (x,w) \in R_L$

The above statement only requires the existence of such $p$, but it does not force it to be explicitly determined. In contrast, for every NP language I know, $p$ is already known:

• For SAT, the size of witness is equal to the number of atoms appearing in the formula.
• For Hamiltonicity, the size of witness is $O(|V|)$, where $V$ is the vertex set.
• For Graph 3-Coloring, the size of witness is $O(|V|)$, where $V$ is the vertex set.

Does there exist an NP language (even an artificial one), for which we know there exist some polynomial $p$ bounding the size of witness, yet we cannot explicitly determine $p$?

• For any given language in NP, there are many NP relations that give rise to it. Are you asking about languages $L$ where the minimal polynomial $p$ is unknown (that is, where we can try to minimize the polynomial by looking at different relations giving rise to the same $L$), or about relations where the corresponding polynomial $p$ is unknown (but we know one exists)? – Joshua Grochow Oct 18 '10 at 4:58
• @Joshua: I might be misunderstanding your comment, but if we know the minimal $p$ over all relations for some NP-complete problem and if it is non-zero, doesn't that mean $P\neq NP$? – Cong Han Oct 18 '10 at 5:21
• @Cong: You're right. I guess I meant the minimal p we know of, say, modulo standard assumptions/current state of the art. For example, I believe Ryan Williams's STOC 2010 paper shows that if there is a relation for SAT with witness size $o(n)$, then $NEXP \not\subseteq P/poly$, so showing such a thing is beyond current understanding. – Joshua Grochow Oct 18 '10 at 5:38
• @Joshua: Right, of course! Got it thanks. – Cong Han Oct 18 '10 at 5:54
• If there's a relation for Circuit SAT with witness size $k-\omega(\log n)$, where $k$ is the number of inputs to the circuit and $n$ is the size of the circuit, then yes, $NEXP \not\subseteq P/poly$. – Ryan Williams Oct 18 '10 at 6:09

Now construct some problem in NP where the witness is of size $O(n^k)$. Off the top of my head I can't think of a nice way of doing this, but here's one way. Let the input be a succinct description of a graph. Since the description size is n, the graph is on exponentially many vertices. (For example, maybe the input is a circuit that accepts two inputs x and y and tells you if (x,y) is an edge in the graph.) The question is to determine if the graph contains a path of length $n^k$. This problem is in NP because the prover can send the list of vertices on the path in order, which the verifier can check. The size of the witness is $n^k$.