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

PDF
BibTeX
XML
Cite

\textit{L. G. Valiant} and \textit{V. V. Vazirani}, Theor. Comput. Sci. 47, 85--95 (1986; Zbl 0621.68030)

Full Text:
DOI

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

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.