26
$\begingroup$

It occurred to many that in all the $\textbf{NP}$-completeness proofs I've read (that I can remember), it's always trivial to show that a problem is in $\textbf{NP}$, and showing that it is $\textbf{NP}$-hard is the... hard part. What $\textbf{NP}$-complete problems are these whose polynomial-time verifiers are highly non-trivial?

$\endgroup$
  • 9
    $\begingroup$ Not NP-complete, but showing membership in NP of testing whether a number is prime is quite non-trivial (rather than showing that it's a composite, which is trivial). The problem is of course known to be in P by now, but still, this is an intriguing verifier. $\endgroup$ – Shaull Jun 19 '14 at 10:18
  • 2
    $\begingroup$ Proving the "PRIME" is in NP was definitely a lot harder than proving that most NP-complete problems are in NP. $\endgroup$ – gnasher729 Jun 19 '14 at 17:12
  • 1
    $\begingroup$ See also the more general question cstheory.stackexchange.com/q/21106/109 over at CS.SE. $\endgroup$ – András Salamon Jun 22 '14 at 20:39
19
$\begingroup$

There are at least four such $NP$-complete problems listed in the appendix of Garey and Johnson's COMPUTERS AND INTRACTABILITY: A Guide to the Theory of NP-Completeness.

[AN6] NON-DIVISIBILITY OF A PRODUCT POLYNOMIAL

INSTANCE: Sequences $A_i = \langle (a_i[1],b_i[1]), ..., (a_i[k],b_i[k]) \rangle,\ 1 \leqslant i \leqslant m,$ of pairs of integers, with each $b_i[j] \geqslant 0,$ and an integer $N$.

QUESTION: Is $\displaystyle \prod_{i=1}^m \left( \displaystyle\sum_{j=1}^k a_i[j] \cdot z^{b_i[j]} \right)$ not divisible by $z^N - 1$?

Reference: [Plaisted, 1977a], [Plaisted, 1977b]. Transformation from 3SAT. Proof of membership in NP is non-trivial and appears in the second reference.

The other three I found in the appendix are:

  • [LO13] MODAL LOGIC S5-SATISFIABILITY
  • [LO19] SECOND ORDER INSTANTIATION
  • [MS3] NON-LIVENESS OF FREE CHOICE PETRI NETS
$\endgroup$
  • $\begingroup$ Thanks! I have this book so I'll make sure to check those out. $\endgroup$ – gardenhead Jun 22 '14 at 23:55
  • $\begingroup$ I am a bit unclear regarding this problem: (1) Am I correct in interpreting z is a variable that can take any integer value (just like an ordinary linear/quadratic equation). (2) Thus, the non-divisibility would be equivalent o stating that: "for no integer value of z equation A is divisible by B"? $\endgroup$ – TheoryQuest1 May 11 '17 at 18:01
  • 1
    $\begingroup$ What I gathered from skimming the first couple pages of the 1977a paper is that $z$ is a quantity related to the number of zeroes of the polynomial that's part of the input. For more than that, you'll have to slog through the paper, I'm afraid. $\endgroup$ – Kyle Jones May 11 '17 at 18:11
4
$\begingroup$

Here is a problem from the database theory, more specifically, from the serializability theory.

In Serializability by Locking (Page 237), it says that

Regarding the complexity of safety, Papadimitriou et al. [14] showed that it is $\textrm{NP}$-hard to test if a transaction system is not $SSR$-safe, and conjectured that the problem is $\textrm{NP}$. From Theorem 3 (In this paper), it follows that this is true.

The $SSR$-safe problem can be found in the paper "Some Computational Problems Related to Database Concurrency Control" by Papadimitriou et al. Unfortunately, I have no access to it.

$\endgroup$
2
$\begingroup$

For me, Integer Linear Programming (and the related Quantifier Free Presburger Arithmetic) are in this class.

A naive approach to an $n$-dimensional ILP problem is to iterate through all length $n$ vectors of integers. But this is an unbounded process.

You have to use some number theory to prove that there is a polynomial upper bound on the size of solutions, meaning that if a solution exists, there is always a polynomially-sized solution, which acts as a certificate.

More information can be found in the answer to a question I asked a while back.

$\endgroup$

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.