Thumbnail
Access Restriction
Open

Author Faber, Wolfgang ♦ Ricca, Francesco
Source CiteSeerX
Content type Text
Publisher Springer Verlag
File Format PDF
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Disjunctive Logic Program ♦ Previous Heuristic ♦ Qbf Solver Ssolve ♦ New Heuristic Hds ♦ Conditional Planning ♦ Hard Asp Program ♦ Extensive Experiment ♦ Recent Research ♦ Well-assessed Heuristic ♦ Hard Program ♦ 2-complete Problem ♦ Dlv System ♦ Several Important Ai Problem ♦ Qbf Evaluation ♦ Asp System Dlv ♦ Np Problem ♦ 2-hard Asp Program ♦ Asp System ♦ Benign Behaviour
Description Recent research on answer set programming (ASP) systems, has mainly focused on solving NP problems more efficiently. Yet, disjunctive logic programs allow for expressing every problem in the complexity classes Σ P 2 and Π P 2. These classes are widely believed to be strictly larger than NP, and several important AI problems, like conformant and conditional planning, diagnosis and more are located in this class. In this paper we focus on improving the evaluation of Σ P 2 /Π P 2-hard ASP programs. To this end, we define a new heuristic hDS and implement it in the (disjunctive) ASP system DLV. The definition of hDS is geared towards the peculiarites of hard programs, while it maintains the benign behaviour of the well-assessed heuristic of DLV for NP problems. We have conducted extensive experiments with the new heuristic. hDS significantly outperforms the previous heuristic of DLV on hard 2QBF problems. We also compare the DLV system (with hDS) to the QBF solvers SSolve, Quantor, Semprop, and yQuaffle, which performed best in the QBF evaluation of 2004. The results of the comparison indicate that ASP systems currently seem to be the best choice for solving Σ P 2 /Π P 2-complete problems.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Learning Resource Type Article
Publisher Date 2005-01-01
Publisher Institution TERRACINA (EDS.), LOGIC PROGRAMMING AND NONMONOTONIC REASONING — 8TH INTERNATIONAL CONFERENCE, LPNMR’05, DIAMANTE, ITALY, SEPTEMBER 2005, PROCEEDINGS