7

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?
Command Master
  • 484
  • 2
  • 10
  • 3
    Maybe related: https://cstheory.stackexchange.com/questions/21106/nontrivial-membership-in-np?rq=1 – Lamine Jun 21 '23 at 17:14

2 Answers2

7

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.

Mark Schultz-Wu
  • 978
  • 4
  • 13
5

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.

Mark S
  • 1,083
  • 6
  • 20
  • 2
    In a similar vein, the existential theory of the complex field is in NP contingent on the extended Riemann hypothesis and AM = NP. – Emil Jeřábek Jun 21 '23 at 20:05
  • @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? – Mark S Jun 21 '23 at 20:28
  • Just if, not iff. The paper is https://doi.org/10.1006/jcom.1996.0019 . – Emil Jeřábek Jun 21 '23 at 20:37
  • 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. – Mark S Jun 21 '23 at 20:43
  • Concerning the terminology, calling it "Nullstellensatz" frankly does not make much sense to me. It screams "type check error", as the Nullstellensatz is a theorem (that's what "Satz" means), not a computational problem. And if I were to associate a problem to the NSS, the most natural choice would be very different: something like "given a set of polynomials $f_i$ with no common complex zero, find polynomials $g_i$ such that $\sum_if_ig_i=1$". In contrast, "existential theory of $\mathbb C$" is a perfectly sound description, and it agrees with the established "existential theory of reals". – Emil Jeřábek Jun 22 '23 at 05:34
  • 1
    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. – Emil Jeřábek Jun 22 '23 at 05:46