Abstract: Determining the existence of answer sets of logic programs is a key problem in answer set programming, and is also NP-complete. Current methods for determining the existence of answer sets are mainly based on the evenness/oddness of the number of edges in negative circles.The limitation of this kind of methods is that if a normal logic program is not stratified, the existence of answer sets of the program cannot be accurately determined. A novel negative circle based method was proposed to solve this problem. An algorithmic framework and the correctness of the method were presented in this paper, and its effectiveness was illustrated by example analysis.

Key words: Answer set programming, Answer set, Splitting set, Negative cycle