Isomorphic implication

DOI10.1007/S00224-007-9038-1MaRDI QIDQ2272203zbMATH OpenOpenAlexFDO

Authors 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 complexityconstraintsisomorphism problemlogic in computer sciencepropositional logic

Mathematics Subject Classification ID

Classical propositional logic (03B05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25)

Abstract: We study the isomorphic implication problem for Boolean constraints. We show that this is a natural analog of the subgraph isomorphism problem. We prove that, depending on the set of constraints, this problem is in P, NP-complete, or NP-hard, coNP-hard, and in parallel access to NP. We show how to extend the NP-hardness and coNP-hardness to hardness for parallel access to NP for some cases, and conjecture that this can be done in all cases.

Recommendations

• Mathematical Foundations of Computer Science 2005
• STACS 2004
• scientific article; zbMATH DE number 1948177
• The Formula Isomorphism Problem
• The complexity of propositional implication

Cites work

• A dichotomy theorem for maximum generalized satisfiability problems.
• Closure properties of constraints
• Complexity classifications of Boolean constraint satisfaction problems
• Complexity of generalized satisfiability counting problems
• Exact analysis of Dodgson elections
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 477971 (Why is no real title available?)
• scientific article; zbMATH DE number 1948177 (Why is no real title available?)
• scientific article; zbMATH DE number 1390075 (Why is no real title available?)
• More complicated questions about maxima and minima, and some closures of NP
• On the computational complexity of some classical equivalence relations on boolean functions
• On truth-table reducibility to SAT
• Recursively enumerable sets of positive integers and their decision problems
• STACS 2004
• The approximability of constraint satisfaction problems
• The complexity of minimal satisfiability problems
• The complexity of satisfiability problems
• The complexity of theorem-proving procedures
• The Formula Isomorphism Problem
• The Inverse Satisfiability Problem
• The Minimization Problem for Boolean Formulas

Cited in

(2)

• STACS 2004
• Mathematical Foundations of Computer Science 2005

This page was built for publication: Isomorphic implication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2272203)