<p>If you don't mind artificial languages, we can construct such problems using pretty much any number k whose value is unknown to mathematicians. For example, we don't know the value of R(5,5) (the fifth <a href="http://en.wikipedia.org/wiki/Ramsey_number#Ramsey_numbers">Ramsey number</a>), or the size of the largest excluded minor of the family of knotless graphs (this number is finite due to the <a href="http://en.wikipedia.org/wiki/Robertson-Seymour_theorem">Robertson-Seymour theorem</a>), or the value of BB(10), where BB() stands for the <a href="http://en.wikipedia.org/wiki/Busy_beaver">Busy Beaver function</a>. Let k equal any of these numbers. We know that k is finite, but we don't know the value of k.</p>

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

CC BY-SA 2.5
2010-10-18T04:30:00.563Z
2010-10-18T04:30:00.563Z
Robin Kothari
<p>The question occurred to me when I get Dana Moshkovitz answer to <a href="https://cstheory.stackexchange.com/q/2247/873">another topic</a>.</p>

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

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

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

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

<blockquote>
  <p>Does there exist an <strong>NP</strong> 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$?</p>
</blockquote>

CC BY-SA 2.5
2010-10-18T04:58:40.550Z
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
CC BY-SA 2.5
2010-10-18T05:21:53.807Z
@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
CC BY-SA 2.5
2010-10-18T05:38:30.717Z
@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
CC BY-SA 2.5
2010-10-18T05:54:04.790Z
@Joshua: Right, of course! Got it thanks.
Cong Han
CC BY-SA 2.5
2010-10-18T06:09:01.380Z
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
<cc.complexity-theory><np>
Is the Witness Size of Membership for Every NP Language Already Known?
Sadeq Dousti
# Is the Witness Size of Membership for Every NP Language Already Known?

(Asked by: username_0 on 2010-10-18)

The question occurred to me when I get Dana Moshkovitz answer to [another topic](https://cstheory.stackexchange.com/q/2247/873).

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$?

**Tags:** cc.complexity-theory, np
> **Comments:**
> **username_1**: 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)?  
> **username_2**: @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$?  
> **username_1**: @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.  
> **username_2**: @Joshua: Right, of course! Got it thanks.  
> **username_3**: 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$.  

---

## 1 answers

### Answer by username_4 on 2010-10-18. Score: 13 | Accepted answer

If you don't mind artificial languages, we can construct such problems using pretty much any number k whose value is unknown to mathematicians. For example, we don't know the value of R(5,5) (the fifth [Ramsey number](http://en.wikipedia.org/wiki/Ramsey_number#Ramsey_numbers)), or the size of the largest excluded minor of the family of knotless graphs (this number is finite due to the [Robertson-Seymour theorem](http://en.wikipedia.org/wiki/Robertson-Seymour_theorem)), or the value of BB(10), where BB() stands for the [Busy Beaver function](http://en.wikipedia.org/wiki/Busy_beaver). Let k equal any of these numbers. We know that k is finite, but we don't know the value of k.

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


---

