28
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 13
    $\begingroup$ 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$. $\endgroup$
    – Artem Kaznatcheev ♦
    Feb 17 '14 at 14:25
  • $\begingroup$ ah interesting, I didn't think about primality certificates. $\endgroup$
    – Denis
    Feb 17 '14 at 14:41
  • 6
    $\begingroup$ 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. $\endgroup$
    – Arnaud
    Feb 17 '14 at 14:42
  • $\begingroup$ 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: rjlipton.wordpress.com/2009/09/02/the-orbit-problem $\endgroup$
    – Jagadish
    Feb 17 '14 at 17:05
  • 3
    $\begingroup$ 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. $\endgroup$
    – Jagadish
    Feb 17 '14 at 17:31
20
$\begingroup$

Integer Programming.

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

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ See Christos Papadimitriou, On the Complexity of Integer Programming, JACM 28 765–768. dx.doi.org/10.1145/322276.322287 (it is worth reading, and only four pages long). $\endgroup$
    – András Salamon
    Feb 17 '14 at 22:08
  • 1
    $\begingroup$ If you don't have access to ACM DL you can obtain Papadimitriou's paper from here. $\endgroup$
    – Kaveh
    Feb 20 '14 at 5:20
18
$\begingroup$

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.

Improve this answer
$\endgroup$
13
$\begingroup$

My favourite example is a classic 1977 result of Ashok 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, shown undecidable by Church and Turing in 1936.)

To avoid undecidability, a 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

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, 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.

Improve this answer
$\endgroup$
5
$\begingroup$

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)

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! :-)

Improve this answer
$\endgroup$
5
$\begingroup$

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 )

Improve this answer
$\endgroup$
4
$\begingroup$

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:

Improve this answer
$\endgroup$
3
$\begingroup$

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...

Improve this answer
$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$
    – Joshua Grochow
    Feb 23 '14 at 15:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.