# Problems in NP with non-trivial certificate

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?

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.

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.

• In a similar vein, the existential theory of the complex field is in NP contingent on the extended Riemann hypothesis and AM = NP. Jun 21, 2023 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? Jun 21, 2023 at 20:28
• Just if, not iff. The paper is doi.org/10.1006/jcom.1996.0019 . Jun 21, 2023 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. Jun 21, 2023 at 20:43
• 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. Jun 22, 2023 at 5:46