查看文章

Answer Set Programming (ASP) is an active research area of artificial intelligence. We consider the problem projected answer set counting (# PDA) for disjunctive propositional ASP.# PDA asks to count the number of answer sets with respect to a given set of projected atoms, where multiple answer sets that are identical when restricted to the projected atoms count as only one projected answer set. Our approach exploits small treewidth of the primal graph of the input instance. Finally, we state a hypothesis (3ETH) that one cannot solve 3-QBF in polynomial time in the instance size while being significantly better than triple exponential in the treewidth. Taking 3ETH into account, we show that one can not expect to solve# PDA significantly better than triple exponential in the treewidth.