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?
26
$\begingroup$
$\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$
$\endgroup$
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
-
$\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$
$\endgroup$
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.
2
$\begingroup$
$\endgroup$
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.
