Program completion as constraint satisfaction : tight logic programs revisited

![CDATA[Research in logic programming shows an increasing interest in studying tight logic programs because as Fages proved, each stable model of a tight logic program is identical to a logic model of a corresponding propositional theory (called the Clark’s completion of the program), and vice versa. Therefore, any algorithms for solving the satisfiability problem may be used to compute stable models of tight logic programs. Furthermore, it has been also observed that many important problems can be encoded into tight logic programs. However, it is still unclear whether we can give a better characterization on the tractability of tight logic programs although some obvious tractable subclass is easy to be recognized. In this paper, we investigate the computational complexity of propositional tight logic programs under stable model semantics. In particular, we provide explicit syntactic characterizations for various tractable subclasses of tight logic programs. Our approach is to transform the completions of tight logic programs to instances of the constraint satisfaction problem (CSP), and then apply Schaefer’s Dichotomy Theorem to obtain sufficient tractability conditions for tight logic programs. Based on this approach, we further specify an interesting subclass of tight logic programs whose computational tractability may be decided through their decompositions.]]