13
$\begingroup$

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

Improve this question
$\endgroup$
5
  • $\begingroup$ 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)? $\endgroup$
    – Joshua Grochow
    Commented Oct 18, 2010 at 4:58
  • $\begingroup$ @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$? $\endgroup$
    – Cong Han
    Commented Oct 18, 2010 at 5:21
  • $\begingroup$ @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. $\endgroup$
    – Joshua Grochow
    Commented Oct 18, 2010 at 5:38
  • $\begingroup$ @Joshua: Right, of course! Got it thanks. $\endgroup$
    – Cong Han
    Commented Oct 18, 2010 at 5:54
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Ryan Williams
    Commented Oct 18, 2010 at 6:09

1 Answer 1

Reset to default
13
$\begingroup$

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), or the size of the largest excluded minor of the family of knotless graphs (this number is finite due to the Robertson-Seymour theorem), or the value of BB(10), where BB() stands for the Busy Beaver function. 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$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.