Isomorphic Implication
<|reference_start|>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, 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.<|reference_end|>
@article{bauland2004isomorphic,
    title={Isomorphic Implication},
    author={Michael Bauland and Edith Hemaspaandra},
    journal={arXiv preprint arXiv:cs/0412062},
    year={2004},
    archivePrefix={arXiv},
    eprint={cs/0412062},
    primaryClass={cs.CC}
}