Isomorphic Implication

Details Isomorphic Implication Isomorphic Implication

2004-12-14

arxiv.org/abs/cs/0412062v2

Computer Science

Computational Complexity

22 pages; corrected typos and minor errors

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Isomorphic Implication does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Isomorphic Implication, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Isomorphic Implication will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-226848