3
$\begingroup$

I believe that a standard way to prove that a language $L$ is in NP is to explicitly construct a witness $y$ for any instance $x$ in $L$ and an efficient algorithm that uses the witness to show that the instance $x$ is in $L$.

But are there any problems in NP for which we have non-constructively proven the existence of a verifier $M$, but we have not yet found any explicit construction for such a verifier?

I don't just mean that "we've roughly sketched out the description of a verifier, but we haven't bothered to fill in all the details required to formalize it as a Turing Machine"; I mean that we genuinely don't know how any specific $M$ would work.

If such a problem existed, then it would be an example of a problem in NP whose solutions are not efficiently verifiable in practice, thereby showing that the heuristic definition of NP as "the set of problems for which we can efficiently verify solutions" is not quite correct.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

For any fixed minor-closed graph family $\mathcal G$, there exists an $O(n^3)$-time algorithm that checks whether a graph $G$ is in $\mathcal G$.

The Robertson–Seymour proof is non-constructive in that it guarantees a finite set of forbidden minors exists without providing a general way to compute it from an arbitrary description of $\mathcal G$.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ And no one has separately found such an algorithm (or any other slower algorithm) for checking whether a graph $G$ is in $\mathcal{G}$? $\endgroup$ Commented yesterday
  • $\begingroup$ Kobayashi, Kawarabashi, and Reed improved the bound to $O(n^2)$, IIRC. $\endgroup$ Commented yesterday
  • 2
    $\begingroup$ Sorry, I mangled the name of one of the authors: it’s Kawarabayashi, Kobayashi & Reed. And as I learned on Wikipedia, there is an explicit linear time algorithm by Mohar for testing whether a graph embeds in a fixed surface, not relying on Robertson and Seymour. So I don’t actually know an example of an explicit minor-closed family for which no explicit poly-time algorithm is known. $\endgroup$ Commented yesterday
  • 1
    $\begingroup$ @EmilJeřábek I think the question is, is there any fixed $\mathcal{G}$ for which no explicit verifier algorithm is known? Is there any good candidate for such a $\mathcal{G}$? (It seems plausible that we might be able to construct an explicit verifier even if we don't know what the set of forbidden minors is, so it's not enough to exhibit a $\mathcal{G}$ for which we don't know the set of forbidden minors, though that might be a good start.) $\endgroup$ Commented 20 hours ago
  • 1
    $\begingroup$ @D.W. Yes, that is the question. And it’s perfectly possible there are good examples of such $\mathcal G$ somewhere; I’m simply not familiar with literature on graph algorithms and graph theory. When I wrote that I don’t know such an example in the comment above, this should be literally taken as a statement of my ignorance, not about the state of affairs in the field. $\endgroup$ Commented 20 hours ago

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.