<p>While the problem "is the crossing number of a graph at most $k$?" is trivially in NP, 
the NP-membership of the related problems for the <em>rectilinear crossing number</em> and 
the <em>pair crossing number</em> are highly not obvious; 
cf. Bienstock, Some probably hard crossing number problems, Discrete Comput. Geometry 6 (1991) 443-459, and 
Schaefer et al., Recognizing string graphs in NP, J. Comput. System Sci. 67 (2003) 365-380.</p>

CC BY-SA 3.0
2014-02-17T23:21:55.010Z
2014-02-17T23:21:55.010Z
user13136
<p>My favourite example is a classic 1977 result of <a href="https://en.wikipedia.org/wiki/Ashok_K._Chandra">Ashok Chandra</a> and Philip Merlin.  They showed that the query containment problem was decidable for conjunctive queries.  The conjunctive query containment problem turns out to be equivalent to deciding whether there is a homomorphism between the two input queries.  This rephrases a semantics problem, involving quantification over an infinite set, into a syntactic one, requiring only checking a finite number of possible homomorphisms.  The homomorphism certificate is only of linear size and so the problem is in NP.</p>

<hr>

<p>This theorem provides one of the foundations of the theory of database query optimization.  The idea is to transform a query into another, faster one.  However, one wants an assurance that the optimization process doesn't create a new query that fails to give answers on some databases where the original query did produce results.</p>

<p>Formally, a <em>database query</em> is an expression of the form $\mathbf{x}.Q(\mathbf{x},\mathbf{y})$, where $\mathbf{x}$ is a list of free variables, $\mathbf{y}$ is a list of bound variables, and $Q(\mathbf{x},\mathbf{y})$ is a first-order formula with variables $\mathbf{x}$ and $\mathbf{y}$ of a language with relation symbols.  The query $Q$ may contain existential and universal quantifiers, the formula may contain conjunction and disjunction of relational atoms, and negation may also appear.  A query is applied to a database instance $I$, which is a set of relations.  The result is a set of tuples; when tuple $\mathbf{t}$ in the result is substituted for $\mathbf{x}$ then the formula $Q(\mathbf{t},\mathbf{y})$ can be satisfied.  One can then compare two queries: $Q_1$ is contained in $Q_2$ if whenever $Q_1$ applied to an arbitrary database instance $I$ produces some results, then $Q_2$ applied to the same instance $I$ also produces some results.  (It is OK if $Q_1$ doesn't produce results but $Q_2$ does, but for containment the implication must hold for every possible instance.)
The <strong>query containment problem</strong> asks: given two database queries $Q_1$ and $Q_2$, is $Q_1$ contained in $Q_2$?</p>

<p>It was not at all clear before Chandra-Merlin that the problem was decidable.  Using just the definition, one has to quantify over the infinite set of all possible databases.  If the queries are unrestricted, then the problem is, in fact, undecidable: let $Q_1$ be a formula that is always true, then $Q_1$ is contained in $Q_2$ iff $Q_2$ is valid.  (This is Hilbert's <a href="https://en.wikipedia.org/wiki/Entscheidungsproblem">Entscheidungsproblem</a>, shown undecidable by Church and Turing in 1936.)</p>

<p>To avoid undecidability, a <a href="https://en.wikipedia.org/wiki/Conjunctive_query">conjunctive query</a> has a rather limited form: $Q$ only contains existential quantifiers, and negation and disjunction are not allowed.  So $Q$ is a positive existential formula with only conjunction of relational atoms.  This is a tiny fragment of logic, but it is enough to express a large proportion of useful database queries.  The classic <code>SELECT ... FROM</code> statement in SQL expresses conjunctive queries; most search engine queries are conjunctive queries.</p>

<p>One can define homomorphisms between queries in a straightforward way (similar to graph homomorphism, with a bit of extra bookkeeping).  The Chandra-Merlin theorem says: given two conjunctive queries $Q_1$ and $Q_2$, $Q_1$ is contained in $Q_2$ iff there is a query homomorphism from $Q_2$ to $Q_1$.  This establishes membership in NP, and it is straightforward to show that this is also NP-hard.</p>

<ul>
<li>Ashok K. Chandra and Philip M. Merlin, <em>Optimal Implementation of Conjunctive Queries in Relational Data Bases</em>, STOC '77 77–90. doi:<a href="http://dx.doi.org/10.1145/800105.803397">10.1145/800105.803397</a></li>
</ul>

<p>Decidability of query containment was later extended to unions of conjunctive queries (existential positive queries where disjunction is allowed), although allowing disjunction raises the complexity to $\Pi^P_2$-complete.  Decidability and undecidability results have also been established for a <a href="https://cstheory.stackexchange.com/a/18867/109">more general form of query containment</a>, involving semiring valuations that occur when counting the number of answers, when combining annotations in provenance, or when combining results of queries in probabilistic databases.</p>

CC BY-SA 3.0
2014-02-17T18:34:31.453Z
2014-02-17T20:18:24.823Z
2014-02-17T20:18:24.823Z
András Salamon
<p>When the recognition of tolerance graph recognition was open, the following paper showed that it is in NP:</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/S0166218X04000940" rel="noreferrer">http://www.sciencedirect.com/science/article/pii/S0166218X04000940</a></p>

<p>(Later on, tolerance graph recognition was shown to be NP complete: <a href="http://arxiv.org/abs/1001.3251" rel="noreferrer">http://arxiv.org/abs/1001.3251</a> )</p>

CC BY-SA 3.0
2014-02-19T18:56:01.000Z
2014-02-19T18:56:01.000Z
JimN
<p>I found a good candidate while reading some papers about quadratic diophantine equations:</p>

<p><a href="http://arxiv.org/abs/math/0611209" rel="noreferrer">J. C. Lagarias, Succinct certificates for solutions to binary quadratic Diophantine equations (2006)</a></p>

<p>From the abstract: ... Let $L(F)$ denote the length of the binary encoding of the binary quadratic Diophantine
equation $F$ given by $a x_1^2 +b x_1 x_2+ c x_2^2 +d x_1+e x_2 + f = 0$. Suppose $F$ is such an equation having a nonnegative integer solution. This paper shows that there is a proof (i.e., “certificate”) that $F$ has such a solution which can be checked in $O(L(F)^5 \log L(F) \log \log L(F))$ bit operations.
A corollary of this result is that the set  $\Sigma = \{F : F \text{ has a nonnegative integer solution}\}$ is in
the complexity class NP ...</p>

<p>... but - to be honest - the only evidence that I have that it is nontrivial is the number of the pages of the paper ... 62! :-)</p>

CC BY-SA 3.0
2014-02-17T22:33:46.253Z
2014-02-17T22:33:46.253Z
Marzio De Biasi
<p>Deciding reachability for various kinds of infinite-state systems is sometimes decidable, often not.  For some interesting special cases a small enough and efficiently checkable certificate always exists, putting such problems into NP.  Here is a neat treatment for one-counter parametric automata:</p>

<ul>
<li>Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, <em>Reachability in succinct and parametric one-counter automata</em>, CONCUR 2009, LNCS 5710 369–383. doi:<a href="http://dx.doi.org/10.1007/978-3-642-04081-8_25" rel="nofollow">10.1007/978-3-642-04081-8_25</a> (<a href="http://www.cs.ox.ac.uk/files/2833/iandc.pdf" rel="nofollow">extended version</a>)</li>
</ul>

CC BY-SA 3.0
2014-02-17T19:11:34.530Z
2014-02-17T19:11:34.530Z
András Salamon
<p>Here is an example (though admittedly artificial) when it is very hard to decide whether a problem is in $NP$ or not. Let $L_1, L_2$ be two languages, with $L_1\in NP$, and $L_2\notin NP$. Now define the language $L$, as follows:</p>

<p>$$L=L_1 \; \mbox{if the twin prime conjecture is true, and } \;
L=L_2 \; \mbox{otherwise}$$ </p>

<p>Then $L\in NP$ precisely if  the twin prime conjecture is true. Since the conjecture is  either true or not, it is indeed well defined whether $L\in NP$ or not. However, deciding which is the case, that is, deciding membership in $NP$,  amounts to solving the famous twin prime conjecture, so it is certainly nontrivial...</p>

CC BY-SA 3.0
2014-02-23T15:41:08.590Z
It's not just artificial, but artificial in a sort of funny way: you haven't given a TM that decides L, but rather more like "If [twin prime conjecture], then the TM is A, and otherwise it's B." You can get a similar artificial example but without this "funniness" as follows: $L = \{x : x \in L_2 \wedge \neg\exists m \leq |x|$ violating the twin primes conjecture$\}$. We can write down a single poly-time nondeterministic TM that decides this language (rather than a conditional statement describing two possible TMs). The resulting language is either $L_2$ or finite.
Joshua Grochow
CC BY-SA 3.0
2014-02-17T22:25:49.477Z
2014-02-17T22:25:49.477Z
Andras Farago
<p><a href="http://en.wikipedia.org/wiki/Integer_programming" rel="nofollow">Integer Programming</a>.</p>

<p>Showing that if there is an integer solution then there is a polynomial size integer solution is quite involved. See </p>

<ul>
<li>Christos Papadimitriou, "<a href="http://dx.doi.org/10.1145/322276.322287" rel="nofollow">On the Complexity of Integer Programming</a>", JACM, 1981.</li>
</ul>

CC BY-SA 3.0
2014-02-17T22:08:27.203Z
See Christos Papadimitriou, _On the Complexity of Integer Programming_, JACM __28__ 765–768.  http://dx.doi.org/10.1145/322276.322287 (it is worth reading, and only four pages long).
András Salamon
CC BY-SA 3.0
2014-02-20T05:20:44.923Z
If you don't have access to ACM DL you can obtain Papadimitriou's paper from [here](http://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf).
Kaveh
CC BY-SA 3.0
2014-02-17T21:58:49.580Z
2014-02-20T05:19:59.170Z
2014-02-20T05:19:59.170Z
Kaveh
<p>Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language?</p>

<p>Instead, the fact that the language is in $NP$ would be proven by reducing it to another language in $NP$, where the link between the two is not trivial and needs careful analysis.</p>

<p>More generally, are there some interesting examples of problems in $NP$ so that it is hard to see that they are in $NP$? </p>

<p>A semi-answer would be the problem of deciding the winner in parity games: to show that it is in $NP$ (even $NP\cap coNP$), we need the positional determinacy theorem which is deep and non-trivial. However this answer is not ideal, because it still boils down to the existence of a polynomial witness for this exact problem (the positional strategy), and does not reduce to another different $NP$-problem.</p>

<p>Another one would be the AKS primality algorithm: deciding whether a number is prime is polynomial, while there is a priori no small witness for this fact. Let's say we rule out the "surprising polynomial algorithms", since many of them would fit the description above. I'm more interested in surprising $NP$ algorithms which are not deterministic.</p>

CC BY-SA 3.0
2014-02-17T14:25:12.027Z
We knew primes was in NP before AKS because $n > 2$ is prime iff there is an $1<r<n$ such that $r^{n−1} = 1 \mod n$ and for all prime divisors q of $n−1$, $r^\frac{n-1}{q} \neq 1 \mod n$.
Artem Kaznatcheev
CC BY-SA 3.0
2014-02-17T14:41:57.147Z
ah interesting, I didn't think about primality certificates.
Denis
CC BY-SA 3.0
2014-02-17T14:42:58.970Z
A good pool for examples of nontrivial membership in NP may come from problems for which it has been open for some time whether they were even decidable. Two problems from the top of my hat : string graph recognition and unknot recognition (and the more general knot genus). In both cases though, there does exist a polynomial witness (namely normal curves/surfaces) - they have just been hard to find. Knottedness is also in NP, and it is also non-trivial: there exists a certificate but one needs the Generalized Riemann Hypothesis to have a polynomial bound on its size.
Arnaud
CC BY-SA 3.0
2014-02-17T17:05:17.630Z
The 'Orbit Problem' was also not known to be decidable for a long time. It was finally proved to be in P. Prof. Lipton has an excellent article on his blog about the history of this problem: http://rjlipton.wordpress.com/2009/09/02/the-orbit-problem/
Jagadish
CC BY-SA 3.0
2014-02-17T17:31:03.107Z
One more example: Given a graph, decide if it is perfect. The problem can be solved in polynomial time, but it took a while to prove that it is in NP.
Jagadish
CC BY-SA 3.0
2014-02-17T18:35:38.897Z
There are some nice answers in the comments...
András Salamon
CC BY-SA 3.0
2014-02-17T22:12:00.863Z
@Jagadish: Moreover, perfect graph recognition is one of those cases where the polynomial-time algorithm also established membership in NP, which was open previously.
András Salamon
<reductions><np>
Nontrivial membership in NP
Denis
# Nontrivial membership in NP

(Asked by: username_0 on 2014-02-17)

Is there an example of a language which is in $NP$, but where we cannot prove this fact directly by showing that there exists a polynomial witness for membership in this language?

Instead, the fact that the language is in $NP$ would be proven by reducing it to another language in $NP$, where the link between the two is not trivial and needs careful analysis.

More generally, are there some interesting examples of problems in $NP$ so that it is hard to see that they are in $NP$?

A semi-answer would be the problem of deciding the winner in parity games: to show that it is in $NP$ (even $NP\cap coNP$), we need the positional determinacy theorem which is deep and non-trivial. However this answer is not ideal, because it still boils down to the existence of a polynomial witness for this exact problem (the positional strategy), and does not reduce to another different $NP$-problem.

Another one would be the AKS primality algorithm: deciding whether a number is prime is polynomial, while there is a priori no small witness for this fact. Let's say we rule out the "surprising polynomial algorithms", since many of them would fit the description above. I'm more interested in surprising $NP$ algorithms which are not deterministic.

**Tags:** reductions, np
> **Comments:**
> **username_1**: We knew primes was in NP before AKS because $n > 2$ is prime iff there is an $1<r<n$ such that $r^{n−1} = 1 \mod n$ and for all prime divisors q of $n−1$, $r^\frac{n-1}{q} \neq 1 \mod n$.  
> **username_0**: ah interesting, I didn't think about primality certificates.  
> **username_2**: A good pool for examples of nontrivial membership in NP may come from problems for which it has been open for some time whether they were even decidable. Two problems from the top of my hat : string graph recognition and unknot recognition (and the more general knot genus). In both cases though, there does exist a polynomial witness (namely normal curves/surfaces) - they have just been hard to find. Knottedness is also in NP, and it is also non-trivial: there exists a certificate but one needs the Generalized Riemann Hypothesis to have a polynomial bound on its size.  
> **username_3**: The 'Orbit Problem' was also not known to be decidable for a long time. It was finally proved to be in P. Prof. Lipton has an excellent article on his blog about the history of this problem: http://rjlipton.wordpress.com/2009/09/02/the-orbit-problem/  
> **username_3**: One more example: Given a graph, decide if it is perfect. The problem can be solved in polynomial time, but it took a while to prove that it is in NP.  
> **username_4**: There are some nice answers in the comments...  
> **username_4**: @Jagadish: Moreover, perfect graph recognition is one of those cases where the polynomial-time algorithm also established membership in NP, which was open previously.  

---

## 7 answers

### Answer by username_10 on 2014-02-17. Score: 20 | Accepted answer

[Integer Programming](http://en.wikipedia.org/wiki/Integer_programming).

Showing that if there is an integer solution then there is a polynomial size integer solution is quite involved. See

* Christos Papadimitriou, "[On the Complexity of Integer Programming](http://dx.doi.org/10.1145/322276.322287)", JACM, 1981.

> **Comments:**
> **username_4**: See Christos Papadimitriou, _On the Complexity of Integer Programming_, JACM __28__ 765–768.  http://dx.doi.org/10.1145/322276.322287 (it is worth reading, and only four pages long).  
> **username_10**: If you don't have access to ACM DL you can obtain Papadimitriou's paper from [here](http://lara.epfl.ch/w/_media/papadimitriou81complexityintegerprogramming.pdf).  

---

### Answer by username_5 on 2014-02-17. Score: 18

While the problem "is the crossing number of a graph at most $k$?" is trivially in NP,
the NP-membership of the related problems for the *rectilinear crossing number* and
the *pair crossing number* are highly not obvious;
cf. Bienstock, Some probably hard crossing number problems, Discrete Comput. Geometry 6 (1991) 443-459, and
Schaefer et al., Recognizing string graphs in NP, J. Comput. System Sci. 67 (2003) 365-380.


---

### Answer by username_4 on 2014-02-17. Score: 13

My favourite example is a classic 1977 result of [Ashok Chandra](https://en.wikipedia.org/wiki/Ashok_K._Chandra) and Philip Merlin. They showed that the query containment problem was decidable for conjunctive queries. The conjunctive query containment problem turns out to be equivalent to deciding whether there is a homomorphism between the two input queries. This rephrases a semantics problem, involving quantification over an infinite set, into a syntactic one, requiring only checking a finite number of possible homomorphisms. The homomorphism certificate is only of linear size and so the problem is in NP.

---

This theorem provides one of the foundations of the theory of database query optimization. The idea is to transform a query into another, faster one. However, one wants an assurance that the optimization process doesn't create a new query that fails to give answers on some databases where the original query did produce results.

Formally, a *database query* is an expression of the form $\mathbf{x}.Q(\mathbf{x},\mathbf{y})$, where $\mathbf{x}$ is a list of free variables, $\mathbf{y}$ is a list of bound variables, and $Q(\mathbf{x},\mathbf{y})$ is a first-order formula with variables $\mathbf{x}$ and $\mathbf{y}$ of a language with relation symbols. The query $Q$ may contain existential and universal quantifiers, the formula may contain conjunction and disjunction of relational atoms, and negation may also appear. A query is applied to a database instance $I$, which is a set of relations. The result is a set of tuples; when tuple $\mathbf{t}$ in the result is substituted for $\mathbf{x}$ then the formula $Q(\mathbf{t},\mathbf{y})$ can be satisfied. One can then compare two queries: $Q\_1$ is contained in $Q\_2$ if whenever $Q\_1$ applied to an arbitrary database instance $I$ produces some results, then $Q\_2$ applied to the same instance $I$ also produces some results. (It is OK if $Q\_1$ doesn't produce results but $Q\_2$ does, but for containment the implication must hold for every possible instance.)
The **query containment problem** asks: given two database queries $Q\_1$ and $Q\_2$, is $Q\_1$ contained in $Q\_2$?

It was not at all clear before Chandra-Merlin that the problem was decidable. Using just the definition, one has to quantify over the infinite set of all possible databases. If the queries are unrestricted, then the problem is, in fact, undecidable: let $Q\_1$ be a formula that is always true, then $Q\_1$ is contained in $Q\_2$ iff $Q\_2$ is valid. (This is Hilbert's [Entscheidungsproblem](https://en.wikipedia.org/wiki/Entscheidungsproblem), shown undecidable by Church and Turing in 1936.)

To avoid undecidability, a [conjunctive query](https://en.wikipedia.org/wiki/Conjunctive_query) has a rather limited form: $Q$ only contains existential quantifiers, and negation and disjunction are not allowed. So $Q$ is a positive existential formula with only conjunction of relational atoms. This is a tiny fragment of logic, but it is enough to express a large proportion of useful database queries. The classic `SELECT ... FROM` statement in SQL expresses conjunctive queries; most search engine queries are conjunctive queries.

One can define homomorphisms between queries in a straightforward way (similar to graph homomorphism, with a bit of extra bookkeeping). The Chandra-Merlin theorem says: given two conjunctive queries $Q\_1$ and $Q\_2$, $Q\_1$ is contained in $Q\_2$ iff there is a query homomorphism from $Q\_2$ to $Q\_1$. This establishes membership in NP, and it is straightforward to show that this is also NP-hard.

* Ashok K. Chandra and Philip M. Merlin, *Optimal Implementation of Conjunctive Queries in Relational Data Bases*, STOC '77 77–90. doi:[10.1145/800105.803397](http://dx.doi.org/10.1145/800105.803397)

Decidability of query containment was later extended to unions of conjunctive queries (existential positive queries where disjunction is allowed), although allowing disjunction raises the complexity to $\Pi^P\_2$-complete. Decidability and undecidability results have also been established for a [more general form of query containment](https://cstheory.stackexchange.com/a/18867/109), involving semiring valuations that occur when counting the number of answers, when combining annotations in provenance, or when combining results of queries in probabilistic databases.


---

### Answer by username_6 on 2014-02-19. Score: 5

When the recognition of tolerance graph recognition was open, the following paper showed that it is in NP:

<http://www.sciencedirect.com/science/article/pii/S0166218X04000940>

(Later on, tolerance graph recognition was shown to be NP complete: <http://arxiv.org/abs/1001.3251> )


---

### Answer by username_7 on 2014-02-17. Score: 5

I found a good candidate while reading some papers about quadratic diophantine equations:

[J. C. Lagarias, Succinct certificates for solutions to binary quadratic Diophantine equations (2006)](http://arxiv.org/abs/math/0611209)

From the abstract: ... Let $L(F)$ denote the length of the binary encoding of the binary quadratic Diophantine
equation $F$ given by $a x\_1^2 +b x\_1 x\_2+ c x\_2^2 +d x\_1+e x\_2 + f = 0$. Suppose $F$ is such an equation having a nonnegative integer solution. This paper shows that there is a proof (i.e., “certificate”) that $F$ has such a solution which can be checked in $O(L(F)^5 \log L(F) \log \log L(F))$ bit operations.
A corollary of this result is that the set $\Sigma = \{F : F \text{ has a nonnegative integer solution}\}$ is in
the complexity class NP ...

... but - to be honest - the only evidence that I have that it is nontrivial is the number of the pages of the paper ... 62! :-)


---

### Answer by username_4 on 2014-02-17. Score: 4

Deciding reachability for various kinds of infinite-state systems is sometimes decidable, often not. For some interesting special cases a small enough and efficiently checkable certificate always exists, putting such problems into NP. Here is a neat treatment for one-counter parametric automata:

* Christoph Haase, Stephan Kreutzer, Joël Ouaknine, James Worrell, *Reachability in succinct and parametric one-counter automata*, CONCUR 2009, LNCS 5710 369–383. doi:[10.1007/978-3-642-04081-8\_25](http://dx.doi.org/10.1007/978-3-642-04081-8_25) ([extended version](http://www.cs.ox.ac.uk/files/2833/iandc.pdf))


---

### Answer by username_8 on 2014-02-17. Score: 3

Here is an example (though admittedly artificial) when it is very hard to decide whether a problem is in $NP$ or not. Let $L\_1, L\_2$ be two languages, with $L\_1\in NP$, and $L\_2\notin NP$. Now define the language $L$, as follows:

$$L=L\_1 \; \mbox{if the twin prime conjecture is true, and } \;
L=L\_2 \; \mbox{otherwise}$$

Then $L\in NP$ precisely if the twin prime conjecture is true. Since the conjecture is either true or not, it is indeed well defined whether $L\in NP$ or not. However, deciding which is the case, that is, deciding membership in $NP$, amounts to solving the famous twin prime conjecture, so it is certainly nontrivial...

> **Comments:**
> **username_9**: It's not just artificial, but artificial in a sort of funny way: you haven't given a TM that decides L, but rather more like "If [twin prime conjecture], then the TM is A, and otherwise it's B." You can get a similar artificial example but without this "funniness" as follows: $L = \{x : x \in L_2 \wedge \neg\exists m \leq |x|$ violating the twin primes conjecture$\}$. We can write down a single poly-time nondeterministic TM that decides this language (rather than a conditional statement describing two possible TMs). The resulting language is either $L_2$ or finite.  

---

