<p>I feel like problems <span class="math-container">$P\in\mathsf{NP}\cap\mathsf{coNP}$</span> are good examples for your question.
Typically, for <span class="math-container">$P\not\in\mathsf{P}$</span>, at least one of the witnesses is non-trivial.</p>
<p>For example, the closest vector problem <span class="math-container">$\mathsf{CVP}\in\mathsf{NP}$</span> immediately.
Informally, given a description of a lattice <span class="math-container">$L$</span> (i.e. discrete linear combination of vectors), and target point <span class="math-container">$t\in\mathbb{R}^n$</span>, the problem is to determine if there is a nearby lattice point.</p>
<p>There is an easy NP witness for this problem --- describe the nearby lattice point.
The hard part is giving a <span class="math-container">$\mathsf{coNP}$</span> witness, i.e. some witness showing there cannot be a nearby lattice point.
This can be done (see for example <a href="https://cims.nyu.edu/%7Eregev/papers/cvpconp.pdf" rel="noreferrer">this</a>), but it is definitely non-trivial.
So concretely, <span class="math-container">$\mathsf{CVP}_{\sqrt{n}}^c$</span> seems like a decent answer.</p>

CC BY-SA 4.0
2023-06-22T02:31:05.130Z
2023-06-22T02:31:05.130Z
Mark Schultz-Wu
<p>Kuperberg's <a href="https://arxiv.org/abs/1112.0845" rel="noreferrer">certificate of knottedness</a> 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.</p>
<p>I think Kuperberg found some other non-trivial reductions for some Hidden Subgroup Problems, as well.</p>
<p>Also, graph non-isomorphism <em>may</em> be in NP, if AM=NP.</p>

CC BY-SA 4.0
2023-06-21T20:05:30.260Z
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
CC BY-SA 4.0
2023-06-21T20:28:11.903Z
@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
CC BY-SA 4.0
2023-06-21T20:37:04.557Z
Just if, not iff. The paper is https://doi.org/10.1006/jcom.1996.0019 .
Emil Jeřábek
CC BY-SA 4.0
2023-06-21T20:43:39.457Z
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
CC BY-SA 4.0
2023-06-22T05:34:48.547Z
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
CC BY-SA 4.0
2023-06-22T05:46:45.003Z
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](https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis), 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
CC BY-SA 4.0
2023-06-21T18:58:53.880Z
2023-06-21T18:58:53.880Z
Mark S
<p>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:</p>
<ol>
<li>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.</li>
<li>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?</li>
</ol>

CC BY-SA 4.0
2023-06-21T17:14:16.227Z
Maybe related: https://cstheory.stackexchange.com/questions/21106/nontrivial-membership-in-np?rq=1
Lamine
<cc.complexity-theory><soft-question><big-list><np>
Problems in NP with non-trivial certificate
Command Master
# Problems in NP with non-trivial certificate

(Asked by: username_0 on 2023-06-21)

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?

**Tags:** cc.complexity-theory, soft-question, big-list, np

> **Comments:**
> **username_1**: Maybe related: https://cstheory.stackexchange.com/questions/21106/nontrivial-membership-in-np?rq=1  

---

## 2 answers

### Answer by username_2 on 2023-06-22. Score: 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](https://cims.nyu.edu/%7Eregev/papers/cvpconp.pdf)), but it is definitely non-trivial.
So concretely, $\mathsf{CVP}\_{\sqrt{n}}^c$ seems like a decent answer.


---

### Answer by username_3 on 2023-06-21. Score: 5

Kuperberg's [certificate of knottedness](https://arxiv.org/abs/1112.0845) 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.

> **Comments:**
> **username_4**: In a similar vein, the existential theory of the complex field is in NP contingent on the extended Riemann hypothesis and AM = NP.  
> **username_3**: @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?  
> **username_4**: Just if, not iff. The paper is https://doi.org/10.1006/jcom.1996.0019 .  
> **username_3**: 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.  
> **username_4**: 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".  
> **username_4**: 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](https://en.wikipedia.org/wiki/Generalized_Riemann_hypothesis), 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.  

---

