7
$\begingroup$

For all NP-complete problems I can think about, the problem statement says very clearly how to test a certificate. I'm looking for interesting problems with NP which have non-trivial certificates. I can think of two ways for this to happen:

  1. It isn't obvious that the problem is in NP. The only example I can think of is the language of primes which requires (before AKS) primality certificates which are not obvious. However, I'm hoping for languages which are hard (not in BPP) without a certificate.
  2. A certificate can be shorter than the natural certificate. This is the case for many FPT problems, since you can provide a certificate for the kernel. What other languages are there with this property?
$\endgroup$
1

2 Answers 2

7
$\begingroup$

I feel like problems $P\in\mathsf{NP}\cap\mathsf{coNP}$ are good examples for your question. Typically, for $P\not\in\mathsf{P}$, at least one of the witnesses is non-trivial.

For example, the closest vector problem $\mathsf{CVP}\in\mathsf{NP}$ immediately. Informally, given a description of a lattice $L$ (i.e. discrete linear combination of vectors), and target point $t\in\mathbb{R}^n$, the problem is to determine if there is a nearby lattice point.

There is an easy NP witness for this problem --- describe the nearby lattice point. The hard part is giving a $\mathsf{coNP}$ witness, i.e. some witness showing there cannot be a nearby lattice point. This can be done (see for example this), but it is definitely non-trivial. So concretely, $\mathsf{CVP}_{\sqrt{n}}^c$ seems like a decent answer.

$\endgroup$
5
$\begingroup$

Kuperberg's certificate of knottedness of a knot is not entirely trivial, and (I believe still) contingent on the Generalized Riemann Hypothesis. It includes lots of not super-difficult, but not manifestly obvious representation theory. I bet that it carries over to a lot of other similar problems.

I think Kuperberg found some other non-trivial reductions for some Hidden Subgroup Problems, as well.

Also, graph non-isomorphism may be in NP, if AM=NP.

$\endgroup$
6
  • 2
    $\begingroup$ In a similar vein, the existential theory of the complex field is in NP contingent on the extended Riemann hypothesis and AM = NP. $\endgroup$ Commented Jun 21, 2023 at 20:05
  • $\begingroup$ @EmilJeřábek wow! So something like there's an AM protocol to decide $\exists X_1 \cdots \exists X_n \, F(X_1,\dots, X_n)$ for $X_j\in \mathbb C$, but iff the ERH is true? $\endgroup$
    – Mark S
    Commented Jun 21, 2023 at 20:28
  • $\begingroup$ Just if, not iff. The paper is doi.org/10.1006/jcom.1996.0019 . $\endgroup$ Commented Jun 21, 2023 at 20:37
  • $\begingroup$ Oh yes! That famous work of Koiran. Kuperberg leans into it in his knottedness work. I see now your comment. According to GRH (or ERH?) there are enough primes spaced out evenly enough modulo which a system is satisfiable and there's at least one prime that hashes onto $\bf 0$. You refer to the existential theory of the complex field; Koiran referred to the Nullstellensatz; but now I see how they are the same. Kuperberg only needs one prime but Koiran needed a bunch. $\endgroup$
    – Mark S
    Commented Jun 21, 2023 at 20:43
  • 2
    $\begingroup$ Btw, the nomenclature of strengthenings of Riemann's hypothesis varies in the literature. Koiran needs the RH for Dedekind $\zeta$-functions, which most mathematicians, Wikipedia, and myself prefer to call ERH, while GRH often refers to the (weaker) RH for Dirichlet $L$-functions. But some use other terminology; in particular, the influential book of Bach and Shallit uses ERH and GRH with meanings opposite to what I wrote above, and this usage was picked up by most computer scientists. $\endgroup$ Commented Jun 22, 2023 at 5:46

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.