Problem Detail: 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?
Asked By : gardenhead
Answered By : Kyle Jones
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( displaystylesum_{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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/27839
