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