Isomorphic implication

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

zbMATH Keywords

computational complexitypropositional logicconstraintsisomorphism problemlogic in computer science

Mathematics Subject Classification ID

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