Phase Transition in Answer Set Programming

ABSTRACT

The critical behaviors of NP-complete problems have been studied extensively, and numerous results have been obtained for the problems of Boolean formula satisfiability (SAT) and constraint satisfaction (CSP), among others. However, few results are known for the critical behaviors of NP-hard nonmonotonic reasoning problems so far. In this talk we consider random negative two-literal logic programs under the answer set semantics. We prove that under what we call the quadratic model, the problem of whether these random logic programs have answer sets exhibits almost a phase transition. We also show that due to a connection between these random logic programs and random graphs, our result includes as a special case de~la~Vega's theorem on the xistence of kernels in random directed graphs. We report some experimental results, which in turn further justify the theoretical result on phase transition.

BIO

Kewen Wang is currently a professor in the School of Information and Communication Technology at Griffith University, Australia. His research interest is in Knowledge Representation and its applications (specifically, nonmonotonic reasoning, answer set programming and ontologies). He has held academic positions at Tsinghua University in China, Potsdam University in Germany and Hong Kong University of Science and Technology. He visited TU Vienna from Jan to May in 2006.