2004/12/14 by Michael Bauland, Edith Hemaspaandra, Bauland, Michael +1
Computer Science · #Computational Complexity (cs.CC) #F.2.2 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0412062
22 pages; corrected typos and minor errors
arxiv created 2005/04/21 · arxiv updated 2009/12/01
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.