Complexities of Homomorphism and Isomorphism for Definite Logic Programs

A homomorphism φ of logic programs from P to P′ is a function mapping Atoms(P) to Atoms(P′) and it preserves complements and program clause. For each definite program clause a ← a1, ..., an ∈ P it implies that φ(a) ← φ(a1), ..., φ(an) is a program clauses of P′. A homomorphism φ is an isomorphism if φ is a bijection. In this paper, the complexity of the decision problems on homomorphism and isomorphism for definite logic programs is studied. It is shown that the homomorphism problem (HOM-LP) for definite logic programs is NP–complete, and the isomorphism problem (ISO-LP) is equivalent to the graph isomorphism problem (GI). The work is supported by the National Natural Science Foundation of China (Grant Nos. 60310213 and 60463001), the Special Foundation for Improving Scientific Research Condition of Guizhou, and the Government Foundation of Guizhou Province.