On the unique satisfiability problem
From MaRDI portal
Publication:3331209
DOI10.1016/S0019-9958(82)90439-9zbMath0543.03027MaRDI QIDQ3331209
Publication date: 1982
Published in: Information and Control (Search for Journal in Brave)
unique satisfiabilityBoolean formulacomplete problemsoracle machinerelativized complexitytruth assignment
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items (53)
Collapsing degrees via strong computation ⋮ Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete ⋮ NP is as easy as detecting unique solutions ⋮ Unique satisfiability of Horn sets can be solved in nearly linear time ⋮ Multiple total stable models are definitely needed to solve unique solution problems ⋮ The unique Horn-satisfiability problem and quadratic Boolean equations. ⋮ Relativized counting classes: Relations among thresholds, parity, and mods ⋮ Polynomial terse sets ⋮ Simultaneous strong separations of probabilistic and unambiguous complexity classes ⋮ The landscape of communication complexity classes ⋮ Languages polylog-time reducible to dot-depth 1/2 ⋮ The complexity of facets resolved ⋮ Complexity classes without machines: on complete languages for UP ⋮ The expressive power of unique total stable model semantics ⋮ A hierarchy of propositional Horn formuls ⋮ Better approximations of non-Hamiltonian graphs ⋮ Language equations with complementation: decision problems ⋮ Autoreducibility, mitoticity, and immunity ⋮ Limitations of the upward separation technique ⋮ On the Complexity of Master Problems ⋮ On the power of parity polynomial time ⋮ Some rainbow problems in graphs have complexity equivalent to satisfiability problems ⋮ Intersection suffices for Boolean hierarchy equivalence ⋮ Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\) ⋮ Complexity of exclusive nondeterministic finite automata ⋮ Parameterized random complexity ⋮ \(P^{NP[O(\log n)}\) and sparse turing-complete sets for NP] ⋮ The difference and truth-table hierarchies for NP ⋮ Why not negation by fixpoint? ⋮ Complexity of unique list colorability ⋮ Unique (optimal) solutions: complexity results for identifying and locating-dominating codes ⋮ Redundancy in logic. I: CNF propositional formulae ⋮ The complexity of counting edge colorings for simple graphs ⋮ Unique Horn renaming and Unique 2-Satisfiability ⋮ Computing functions with parallel queries to NP ⋮ The complexity of identifying characteristic formulae ⋮ The complexity of unions of disjoint sets ⋮ On the power of parity polynomial time ⋮ Counting classes: Thresholds, parity, mods, and fewness ⋮ Lower bounds and the hardness of counting properties ⋮ Machines that can output empty words ⋮ Counting the number of solutions for instances of satisfiability ⋮ Unnamed Item ⋮ Language equations ⋮ On the computational complexity of determining polyatomic structures by X-rays ⋮ The computational complexity of ideal semantics ⋮ SELF-SPECIFYING MACHINES ⋮ Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help? ⋮ A common algebraic description for probabilistic and quantum computations ⋮ Complexity and expressive power of deterministic semantics for DATALOG\(^ \neg\). ⋮ Restrictive Acceptance Suffices for Equivalence Problems ⋮ A linear time algorithm for unique Horn satisfiability ⋮ Uniquely solvable quadratic Boolean equations
This page was built for publication: On the unique satisfiability problem
