NP is as easy as detecting unique solutions

DOI10.1016/0304-3975(86)90135-0zbMath0621.68030OpenAlexW2057512592WikidataQ55889274 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

cryptography NP-complete problem randomized polynomial time reducibility SAT formula

Mathematics Subject Classification ID

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

Related Items

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, Unnamed Item, Unnamed Item, Dot operators, On the modulo degree complexity of Boolean functions, The Complexity of Symmetric Boolean Parity Holant Problems, 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, Algebraic methods and bounded formulas, Uniqueness of integer solution of linear equations, Parameterized circuit complexity and the $W$ hierarchy, Randomization and the computational power of analytic and algebraic decision trees, Tensor network contractions for \#SAT, Approximate counting in SMT and value estimation for probabilistic programs, Holographic algorithms without matchgates, The complexity of approximating complex-valued Ising and Tutte partition functions, Full spark frames, Parameterized random complexity, On the complexity of unique circuit SAT, On the construction of graphs with a planar bipartite double cover from Boolean formulas and its application to counting satisfying solutions, Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs, Are unique subgraphs not easier to find?, Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems, Complexity and approximability of the cover polynomial, On a theorem of Razborov, Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, A complex analogue of Toda's theorem, On the complexity of ranking, On membership comparable sets, The consequences of eliminating NP solutions, Relations between average-case and worst-case complexity, The complexity of equality constraint languages, The Tutte polynomial modulo a prime, Complexity of unique list colorability, Inapproximability of the Tutte polynomial, An overview of parallel SAT solving, Complexity-sensitive decision procedures for abstract argumentation, Cook's versus Valiant's hypothesis, On quasilinear-time complexity theory, Computing functions with parallel queries to NP, Coloring invariants of knots and links are often intractable, On the theory of average case complexity, On polynomial time one-truth-table reducibility to a sparse set, Polynomial-time 1-Turing reductions from $\#$PH to $\#$P, Generalizations of Opt P to the polynomial hierarchy, On polynomial-time Turing and many-one completeness in PSPACE, Complexity of uniqueness and local search in quadratic 0-1 programming, Probabilistic polynomials, AC$^ 0$ functions and the polynomial-time hierarchy, Arithmetization: A new method in structural complexity theory, Non-deterministic exponential time has two-prover interactive protocols, Deciding uniqueness in norm maximazation, Improving known solutions is hard, The complexity of explicit constructions, The satisfiability threshold for random linear equations, Graph isomorphism is low for PP, On the reducibility of sets inside NP to sets with low information content, Model counting with error-correcting codes, Lower bounds and the hardness of counting properties, Recognizing frozen variables in constraint satisfaction problems, How should we solve search problems privately?, Theoretical and practical fundamentals for multi-objective optimisation in resource-constrained project scheduling problems, Complexity classes of equivalence problems revisited, On complexity of unconstrained hyperbolic 0--1 programming problems, Probability of unique integer solution to a system of linear equations, Computational complexity and 3-manifolds and zombies, Hard promise problems and nonuniform complexity, Cryptanalytic applications of the polynomial method for solving multivariate equation systems over $\mathrm{GF}(2)$, A note on the approximability of deepest-descent circuit steps, Non-commutative arithmetic circuits: depth reduction and size lower bounds, Practical complexities of probabilistic algorithms for solving Boolean polynomial systems, Exploiting functional dependencies in declarative problem specifications, On perturbation resilience of non-uniform $k$-center, Parameterized learnability of juntas, A second step towards complexity-theoretic analogs of Rice's Theorem, The three-color and two-color Tantrix$^{\text{TM}}$ rotation puzzle problems are NP-complete via parsimonious reductions, Intractability results in predicate detection, The computational complexity of ideal semantics, Quantum generalizations of the polynomial hierarchy with applications to $\mathrm{QMA(2)}$, Mind change optimal learning of Bayes net structure from dependency and independency data, CNF satisfiability in a subspace and related problems, Uniform generation of NP-witnesses using an NP-oracle, Mathematical models of quantum computation, Polymer dynamics via cliques: new conditions for approximations, Complexity of probabilistic reasoning in directed-path singly-connected Bayes networks

Cites Work