zbMATH — the first resource for mathematics

NP is as easy as detecting unique solutions. (English) Zbl 0621.68030
For every known NP-complete problem, the number of solutions of its instances varies over a large range, from zero to exponentially many. It is therefore natural to ask if the inherent intractability of NP-complete problems is caused by this wide variation. We give a negative answer to this question using the notion of randomized polynomial time reducibility. We show that the problems of distinguishing between instances of SAT having zero or one solution, or of finding solutions to instances of SAT having a unique solution, are as hard as SAT, under randomized reductions. Several corollaries about the difficulty of specific problems follow. For example, computing the parity of the number of solutions of a SAT formula is shown to be NP-hard, and deciding if a SAT formula has a unique solution is shown to be \(D^ p\)-hard, under randomized reduction. Central to the study of cryptography is the question as to whether there exist NP-problems whose instances have solutions that are unique but are hard to find. Our result can be interpreted as strengthening the belief that such problems exist.

68Q25 Analysis of algorithms and problem complexity
94A60 Cryptography
Full Text: DOI
[1] Adleman, L.M.; Manders, K., Reducibility, randomness and intractability, (), 151-163
[2] Adleman, L.M.; Manders, K., Reductions that Lie, (), 397-410
[3] Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, 305-322, (1977) · Zbl 0356.68059
[4] Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. and control, 55, 80-82, (1982) · Zbl 0543.03027
[5] Carter, J.L.; Wegman, M.N., Universal classes of hash functions, J. comput. system sci., 18, 2, 143-154, (1979) · Zbl 0412.68090
[6] Cook, S.A., The complexity of theorem proving procedures, (), 151-158 · Zbl 0363.68125
[7] Edwards, K.J.; Welsh, D.J.A., On the complexity of unique problems, (1984), Unpublished manuscript
[8] Even, S.; Selman, A.L.; Yacobi, Y., Hardcore theorems for complexity classes, J. ACM, 32, 1, 205-217, (1985) · Zbl 0632.68047
[9] Even, S.; Selman, A.L.; Yacobi, Y., The complexity of promise problems with applications to public-key cryptography, Inform. and control, 61, 2, 159-173, (1984) · Zbl 0592.94012
[10] Even, S.; Yacobi, Y., Cryptography and NP-completeness, (), 195-207 · Zbl 0444.94013
[11] Geske, J.; Grollmann, J., Relativization of unambiguous and random polynomial time classes, (1983), Unpublished manuscript
[12] Grollmann, J.; Selman, A.L., On the existence of secure public-key cryptosystems, (), 495-503
[13] Papadimitriou, C.H.; Yannakakis, M., The complexity of facets (and some facets of complexity), J. comput. system sci., 28, 244-259, (1984) · Zbl 0571.68028
[14] Rackoff, C., Relativized questions involving probabilistic computations, J. ACM, 29, 261-268, (1982) · Zbl 0477.68037
[15] Simon, J., On the difference between one and many, (), 480-491
[16] Sipser, M., A complexity theoretic approach to randomness, (), 330-335
[17] Stockmeyer, L.J., The complexity of approximate counting, (), 118-126
[18] Valiant, L.G., A reduction from satisfiability to Hamiltonian circuits that preserves the number of solutions, (1974), Unpublished manuscript, Leeds
[19] Valiant, L.G., Relative complexity of checking and evaluating, Inform. process. lett., 5, 20-23, (1976) · Zbl 0342.68028
[20] Valiant, L.G., The complexity of computing the permanent, Theoret. comput. sci., 8, 189-201, (1979) · Zbl 0415.68008
[21] L.G. Valiant and V.V. Vazirani, Unpublished manuscript, 1984.
[22] Vazirani, U.V.; Vazirani, V.V., A natural encoding scheme proved probabilistic polynomial complete, Theoret. comput. sci., 24, 291-300, (1983) · Zbl 0525.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.