Isomorphic Implication
| dc.creator | Bauland, Michael | |
| dc.creator | Hemaspaandra, Edith | |
| dc.date | 2004-12-14 | |
| dc.date | 2005-04-21 | |
| dc.date.accessioned | 2026-07-07T03:22:13Z | |
| dc.date.available | 2026-07-07T03:22:13Z | |
| dc.description | 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. | |
| dc.description | 22 pages; corrected typos and minor errors | |
| dc.identifier | https://arxiv.org/abs/cs/0412062 | |
| dc.identifier | http://arxiv.org/abs/cs/0412062 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32511 | |
| dc.subject | Computational Complexity | |
| dc.subject | F.2.2 | |
| dc.title | Isomorphic Implication | |
| dc.type | text |