Isomorphic implication
From MaRDI portal
Publication:2272203
DOI10.1007/s00224-007-9038-1zbMath1173.68024arXivcs/0412062OpenAlexW2913327613MaRDI QIDQ2272203
Michael Bauland, Edith Hemaspaandra
Publication date: 6 August 2009
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0412062
Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A dichotomy theorem for maximum generalized satisfiability problems.
- More complicated questions about maxima and minima, and some closures of NP
- On truth-table reducibility to SAT
- On the computational complexity of some classical equivalence relations on boolean functions
- The complexity of minimal satisfiability problems
- Complexity of generalized satisfiability counting problems
- The Approximability of Constraint Satisfaction Problems
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Exact analysis of Dodgson elections
- The Inverse Satisfiability Problem
- Closure properties of constraints
- The Formula Isomorphism Problem
- The Minimization Problem for Boolean Formulas
- STACS 2004
- The complexity of satisfiability problems
- The complexity of theorem-proving procedures
- Recursively enumerable sets of positive integers and their decision problems