NP is as easy as detecting unique solutions

DOI10.1016/0304-3975(86)90135-0zbMath0621.68030DBLPjournals/tcs/ValiantV86OpenAlexW2057512592WikidataQ55889274 ScholiaQ55889274MaRDI QIDQ1090454

Vijay V. Vazirani, Leslie G. Valiant

Publication date: 1986

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(86)90135-0

zbMATH Keywords

cryptographyNP-complete problemrandomized polynomial time reducibilitySAT formula

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Cryptography (94A60)

Cites Work

• Unnamed Item
• Unnamed Item
• A natural encoding scheme proved probabilistic polynomial complete
• The complexity of computing the permanent
• The complexity of facets (and some facets of complexity)
• Relative complexity of checking and evaluating
• Universal classes of hash functions
• On the unique satisfiability problem
• The complexity of promise problems with applications to public-key cryptography
• Hard-core theorems for complexity classes
• Cryptocomplexity and NP-completeness
• Relativized Questions Involving Probabilistic Algorithms
• On Isomorphisms and Density of $NP$ and Other Complete Sets

Related Items (only showing first 100 items - show all)

Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ Resource-bounded kolmogorov complexity revisited ⋮ The complexity of generating test instances ⋮ The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems ⋮ Unnamed Item ⋮ The Birth and Early Years of Parameterized Complexity ⋮ Nonuniform ACC Circuit Lower Bounds ⋮ On equivalent reformulations for absolute value equations ⋮ Uniform proofs of ACC representations ⋮ On closure properties of bounded two-sided error complexity classes ⋮ On polynomial-time truth-table reducibility of intractable sets to P-selective sets ⋮ The query complexity of witness finding ⋮ Approximately Counting and Sampling Small Witnesses Using a Colorful Decision Oracle ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ The Relative Exponential Time Complexity of Approximate Counting Satisfying Assignments ⋮ On the Complexity of Master Problems ⋮ The complexity of regex crosswords ⋮ Separating counting communication complexity classes ⋮ On the complexity of incremental computation ⋮ Support set selection for abductive and default reasoning ⋮ Elimination Distances, Blocking Sets, and Kernels for Vertex Cover ⋮ Counting vertices of integral polytopes defined by facets ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ A map of witness maps: new definitions and connections ⋮ Structural analysis of the complexity of inverse functions ⋮ The Time Complexity of Constraint Satisfaction ⋮ On the complexity of restoring corrupted colorings ⋮ Testing the satisfiability of algebraic formulas over the field of two elements ⋮ Revisiting time-space tradeoffs for function inversion ⋮ Paradigms for Unconditional Pseudorandom Generators ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Picturing Counting Reductions with the ZH-Calculus ⋮ Barnette's conjecture through the lens of the \(Mod_k P\) complexity classes ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ Inapproximability of the Independent Set Polynomial in the Complex Plane ⋮ A monomial matrix formalism to describe quantum many-body states ⋮ The Three-Color and Two-Color TantrixTM Rotation Puzzle Problems Are NP-Complete Via Parsimonious Reductions ⋮ Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size ⋮ Counting Constraint Satisfaction Problems. ⋮ Predecessor existence problems for finite discrete dynamical systems ⋮ The complexity of Unique \(k\)-SAT: An isolation lemma for \(k\)-CNFs ⋮ Algorithms for modular counting of roots of multivariate polynomials ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Unnamed Item ⋮ On the unique shortest lattice vector problem ⋮ On Toda’s Theorem in Structural Communication Complexity ⋮ Semiring reasoning frameworks in AI and their computational complexity ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Dot operators ⋮ Counting kernels in directed graphs with arbitrary orientations ⋮ Constructive separations and their consequences ⋮ On the modulo degree complexity of Boolean functions ⋮ The Complexity of Symmetric Boolean Parity Holant Problems ⋮ Search-space reduction via essential vertices ⋮ On the power of counting the total number of computation paths of NPTMs ⋮ Quantum advantage from one-way functions ⋮ Unnamed Item ⋮ Weighted counting of solutions to sparse systems of equations ⋮ On sets bounded truth-table reducible to $P$-selective sets ⋮ Monotonous and randomized reductions to sparse sets ⋮ k-SAT Is No Harder Than Decision-Unique-k-SAT ⋮ Depth Reduction for Circuits with a Single Layer of Modular Counting Gates ⋮ Graph isomorphism is low for PP ⋮ The Complexity of the Nucleolus in Compact Games ⋮ On Statistically Secure Obfuscation with Approximate Correctness ⋮ Derandomizing Isolation in Space-Bounded Settings ⋮ Quantum computing and hidden variables ⋮ Does Looking Inside a Circuit Help ⋮ Constant-Round Interactive Proofs for Delegating Computation ⋮ Unique subgraphs are not easier to find ⋮ Function simulation, graph grammars and colourings ⋮ On Super Strong ETH ⋮ Resource bounded symmetry of information revisited ⋮ On the probabilistic closure of the loose unambiguous hierarchy ⋮ Combinatorial techniques for universal hashing ⋮ A taxonomy of complexity classes of functions ⋮ Random generation of combinatorial structures from a uniform distribution ⋮ The fewest clues problem ⋮ Non-deterministic communication complexity with few witnesses ⋮ Sparse sets, approximable sets, and parallel queries to NP ⋮ The power of quantum systems on a line ⋮ Geometric inference for general high-dimensional linear inverse problems ⋮ The relative exponential time complexity of approximate counting satisfying assignments ⋮ Matching is as easy as matrix inversion ⋮ Completeness, approximability and exponential time results for counting problems with easy decision version ⋮ On the hardness of computing the permanent of random matrices ⋮ Polynomial terse sets ⋮ A counterexample to the chain rule for conditional HILL entropy ⋮ The complexity of optimization problems ⋮ The landscape of communication complexity classes ⋮ Nonuniform reductions and NP-completeness ⋮ The complexity of facets resolved ⋮ Promise problems complete for complexity classes ⋮ On the complexity of finding shortest variable disjunction branch-and-bound proofs ⋮ Is Valiant-Vazirani's isolation probability improvable? ⋮ On unique graph 3-colorability and parsimonious reductions in the plane ⋮ The size of SPP ⋮ On building fine-grained one-way functions from strong average-case hardness

This page was built for publication: NP is as easy as detecting unique solutions