Isomorphic Implication
Copyright policy )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.
22 pages; corrected typos and minor errors
- University of Hannover Germany
- Rochester Institute of Technology United States
- Rochester Institute of Technology United States
FOS: Computer and information sciences, computational complexity, isomorphism problem, Analysis of algorithms and problem complexity, Computational Complexity (cs.CC), propositional logic, Classical propositional logic, Computer Science - Computational Complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), logic in computer science, F.2.2, constraints
FOS: Computer and information sciences, computational complexity, isomorphism problem, Analysis of algorithms and problem complexity, Computational Complexity (cs.CC), propositional logic, Classical propositional logic, Computer Science - Computational Complexity, Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.), logic in computer science, F.2.2, constraints
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).2 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!