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

##### MSC:
 68Q25 Analysis of algorithms and problem complexity 94A60 Cryptography
##### MathOverflow Questions:
Complexity of a Diophantine equation having $$\leq1$$ solutions
Full Text:
##### References:
  Adleman, L.M.; Manders, K., Reducibility, randomness and intractability, (), 151-163  Adleman, L.M.; Manders, K., Reductions that Lie, (), 397-410  Berman, L.; Hartmanis, J., On isomorphisms and density of NP and other complete sets, SIAM J. comput., 6, 305-322, (1977) · Zbl 0356.68059  Blass, A.; Gurevich, Y., On the unique satisfiability problem, Inform. and control, 55, 80-82, (1982) · Zbl 0543.03027  Carter, J.L.; Wegman, M.N., Universal classes of hash functions, J. comput. system sci., 18, 2, 143-154, (1979) · Zbl 0412.68090  Cook, S.A., The complexity of theorem proving procedures, (), 151-158 · Zbl 0363.68125  Edwards, K.J.; Welsh, D.J.A., On the complexity of unique problems, (1984), Unpublished manuscript  Even, S.; Selman, A.L.; Yacobi, Y., Hardcore theorems for complexity classes, J. ACM, 32, 1, 205-217, (1985) · Zbl 0632.68047  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  Even, S.; Yacobi, Y., Cryptography and NP-completeness, (), 195-207 · Zbl 0444.94013  Geske, J.; Grollmann, J., Relativization of unambiguous and random polynomial time classes, (1983), Unpublished manuscript  Grollmann, J.; Selman, A.L., On the existence of secure public-key cryptosystems, (), 495-503  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  Rackoff, C., Relativized questions involving probabilistic computations, J. ACM, 29, 261-268, (1982) · Zbl 0477.68037  Simon, J., On the difference between one and many, (), 480-491  Sipser, M., A complexity theoretic approach to randomness, (), 330-335  Stockmeyer, L.J., The complexity of approximate counting, (), 118-126  Valiant, L.G., A reduction from satisfiability to Hamiltonian circuits that preserves the number of solutions, (1974), Unpublished manuscript, Leeds  Valiant, L.G., Relative complexity of checking and evaluating, Inform. process. lett., 5, 20-23, (1976) · Zbl 0342.68028  Valiant, L.G., The complexity of computing the permanent, Theoret. comput. sci., 8, 189-201, (1979) · Zbl 0415.68008  L.G. Valiant and V.V. Vazirani, Unpublished manuscript, 1984.  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.