On the unique satisfiability problem
From MaRDI portal
Recommendations
Cited in
(62)- Better approximations of non-Hamiltonian graphs
- The complexity of identifying characteristic formulae
- Complexity and expressive power of deterministic semantics for DATALOG^ .
- A linear time algorithm for unique Horn satisfiability
- Query-to-communication lifting for \(\mathsf{P}^{\mathsf{NP}}\)
- SELF-SPECIFYING MACHINES
- Uniquely solvable quadratic Boolean equations
- \(P^{NP[O(\log n)]}\) and sparse turing-complete sets for NP
- Polynomial terse sets
- The difference and truth-table hierarchies for NP
- Why not negation by fixpoint?
- Unique (optimal) solutions: complexity results for identifying and locating-dominating codes
- Broadcast graph is NP-complete
- Limitations of the upward separation technique
- The unique Horn-satisfiability problem and quadratic Boolean equations.
- Lower bounds and the hardness of counting properties
- The computational complexity of ideal semantics
- The complexity of facets resolved
- The complexity of counting edge colorings for simple graphs
- Unique satisfiability of Horn sets can be solved in nearly linear time
- A hierarchy of propositional Horn formuls
- Propositional circumscription and extended closed-world reasoning are \(\Pi_ 2^ P\)-complete
- StUSPACE(log n) ⊂-DSPACE(log2 n/log log n)
- A common algebraic description for probabilistic and quantum computations
- Multiple total stable models are definitely needed to solve unique solution problems
- Computing functions with parallel queries to NP
- Autoreducibility, mitoticity, and immunity
- Relativized counting classes: Relations among thresholds, parity, and mods
- Collapsing degrees via strong computation
- Complexity classes without machines: on complete languages for UP
- Language equations with complementation: decision problems
- Counting classes: Thresholds, parity, mods, and fewness
- The landscape of communication complexity classes
- On the complexity of master problems
- A meta-complexity theoretic approach to indistinguishability obfuscation and witness pseudo-canonicalization
- NP is as easy as detecting unique solutions
- Languages polylog-time reducible to dot-depth 1/2
- Counting the number of solutions for instances of satisfiability
- Some rainbow problems in graphs have complexity equivalent to satisfiability problems
- Machines that can output empty words
- Redundancy in logic. I: CNF propositional formulae
- Intersection suffices for Boolean hierarchy equivalence
- Complexity of exclusive nondeterministic finite automata
- The expressive power of unique total stable model semantics
- Language equations
- On the computational complexity of determining polyatomic structures by X-rays
- Complexity of exclusive nondeterministic finite automata
- Complexity of unique list colorability
- On the complexity of determining whether there is a unique Hamiltonian cycle or path
- Parameterized random complexity
- The complexity of deciding characteristic formulae in van Glabbeek's branching-time spectrum
- The complexity of unions of disjoint sets
- scientific article; zbMATH DE number 7561680 (Why is no real title available?)
- scientific article; zbMATH DE number 1775405 (Why is no real title available?)
- On the power of parity polynomial time
- On the power of parity polynomial time
- Simultaneous strong separations of probabilistic and unambiguous complexity classes
- On the complexity of unique circuit SAT
- Restrictive Acceptance Suffices for Equivalence Problems
- Boolean Constraint Satisfaction Problems: When Does Post’s Lattice Help?
- Unique Horn renaming and Unique 2-Satisfiability
- Complexity of unary exclusive nondeterministic finite automata
This page was built for publication: On the unique satisfiability problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3331209)
