NP is as easy as detecting unique solutions. (English) Zbl 0621.68030

Valiant, L. G.; Vazirani, V. V.

Theor. Comput. Sci. 47, 85-95 (1986).

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

Keywords:

NP-complete problem; randomized polynomial time reducibility; SAT formula; cryptography

References:

[1]	Adleman, L. M.; Manders, K., Reducibility, randomness and intractability, (Proc. 9th ACN Symp. on Theory of Computing (1977)), 151-163
[2]	Adleman, L. M.; Manders, K., Reductions that lie, (Proc. 20th IEEE Symp. on Foundations of Computer Science (1979)), 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, (Proc. 3rd ACM Symp. on Theory of Computing (1971)), 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, (Proc. 7th Colloquium on Automata, Languages and Programming. Proc. 7th Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 85 (1980), Springer: Springer Berlin), 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, (Proc. 25th IEEE Symp. on Foundations of Computer Science (1984)), 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, (Colloquium on Automata, Languages and Programming. Colloquium on Automata, Languages and Programming, Lecture Notes in Computer Science, 52 (1977), Springer: Springer Berlin), 480-491
[16]	Sipser, M., A complexity theoretic approach to randomness, (Proc. 15th ACM Symp. on Theory of Computing (1983)), 330-335
[17]	Stockmeyer, L. J., The complexity of approximate counting, (Proc. 15th ACM Symp. on Theory of Computing (1983)), 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
[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