NP is as easy as detecting unique solutions
type: Item
instance of: scholarly article
title: NP is as easy as detecting unique solutions
zbMATH Open document ID: 0621.68030
DOI: 10.1016/0304-3975(86)90135-0
author: Leslie G. Valiant
author: Vijay V. Vazirani
published in: Theoretical Computer Science
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 94A60
zbMATH DE Number: 4007724
zbMATH Keywords: NP-complete problem
zbMATH Keywords: randomized polynomial time reducibility
zbMATH Keywords: SAT formula
zbMATH Keywords: cryptography
Wikidata QID: Q55889274
MaRDI profile type: Publication
full work available at URL: 0304-3975(86)90135-0
OpenAlex ID: W2057512592
cites work: On Isomorphisms and Density of $NP$ and Other Complete Sets
cites work: On the unique satisfiability problem
cites work: Universal classes of hash functions
cites work: Q4138187
cites work: Hard-core theorems for complexity classes
cites work: The complexity of promise problems with applications to public-key cryptography
cites work: Cryptocomplexity and NP-completeness
cites work: The complexity of facets (and some facets of complexity)
cites work: Relativized Questions Involving Probabilistic Algorithms
cites work: Q4139697
cites work: Relative complexity of checking and evaluating
cites work: The complexity of computing the permanent
cites work: A natural encoding scheme proved probabilistic polynomial complete
DBLP publication ID: journals/tcs/ValiantV86
Recommended article: Q4542538
Recommended article: On the complexity of unique solutions
Recommended article: Max NP-completeness made easy
Recommended article: Q5687692
Recommended article: The consequences of eliminating NP solutions
Recommended article: The Simplex Algorithm Is NP-Mighty
Recommended article: On universally easy classes for NP-complete problems
Recommended article: Q4536375
Recommended article: Reducing the number of solutions of NP functions
description: scientific article; zbMATH DE number 4007724