Isomorphic Implication
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, or is NP-complete, or is NP-hard, coNP-hard, and in P (aEuro-) (NP) . We show how to extend the NP-hardness and coNP-hardness to P (aEuro-) (NP) -hardness for some cases, and conjecture that this can be done in all cases.
constraints isomorphism problem computational complexity propositional logic logic in computer science