# Answer Set Programming - Answer Set Programming (ASP) is a [[Imperative vs Declarative Programming#Declarative programming]] approach to logic programming. - You define the program (the problem) using rules of logic programming. - The answer, the "stable model" of the program, consists of all facts that can be derived using the rules of the program. - ASP comes from the combination of databases, logic programming, knowledge representation and satisfiability solving. - How is it different from Prolog? - Prolog will load a file consisting of rules in any order, and display a prompt that invites the user to submit “queries”—questions that can be answered on the basis of the given information. - To write or understand Prolog programs, one has to think not only about their meaning as specifications, but also about Prolog’s search strategy. In that sense, Prolog is not fully declarative; it has an “operational semantics.” - ASP is declarative as there are no "queries" - ASP can be seen as a general-purpose language for representation and reasoning (within limits). - Viewed from the lens of [[Computational Complexity Theory]], ASP is a general approach for NP problems: - Finding answer sets for the basic language of ASP is NP-complete. - The ASP language is convenient for reductions (into ASP) - So it is a good 'canonical, general-purpose problem' (within NP) - With algorithms for ASP, we cover a large class of problems. - When type of problem is symbolic approach well suited for? - Combinatorial problems - Discrete ('crisp') search space - Human readable solutions and problem specification ## Programming with ASP - Programming with CLINGO - https://www.cs.utexas.edu/~vl/teaching/378/pwc.pdf - Provides in-depth explanations and excercise solutions for different levels of combinatorial problems encoded in ASP ## Easy ASP methodology - Videos: https://www.youtube.com/playlist?list=PL7DBaibuDD9O4I05DiQfilqPUgpClMKYu - The answer sets of an easy logic program are the result of applying its rules in order. - The application of choice, normal and constraint rules generates, extends and eliminates answer sets. - A rule is applied in order if for every predicate in its body there are no rules with that predicate in the head left to be applied - Sets of recursive rules are considered as a single rule that is applied repeatedly until nothing changes. - Negative recursion is not allowed. --- ## References