6 - Complexity, expressiveness, and other properties of AnsProlog^* programs

Summary

Earlier in Chapter 3 we discussed several results and properties of AnsProlog^* programs that are useful in analyzing and step-by-step building of these programs. In this chapter we consider some broader properties that help answer questions such as: (a) how difficult is it to compute answer sets of various sub-classes of AnsProlog^*? (b) how expressive are the various sub-classes of AnsProlog^*? (c) does the use of AnsProlog^* lead to compact representation or can it be compiled to a more tractable representation? and (d) what is the relationship between AnsProlog^* and other knowledge representation formalisms?

The answers to these questions are important in many ways. For example, if we know the complexity of a problem that we want to solve then the answer to (a) will tell us which particular subset of AnsProlog^* will be most efficient, and the answer to (b) will tell us the most restricted subset that we can use to represent that problem. With respect to (c) we will discuss results that show that AnsProlog^* leads to a compact representation. This clarifies the misconception that since many AnsProlog^* classes belong to a higher complexity class, they are not very useful. For specifications where AnsProlog^* leads to (exponentially) compact representation the fact that they are computationally harder is canceled out and they become preferable because compact representation means that the programmer has to write less. So the burden is shifted from the programmer to the computer, which is often desirable.