1. Given a domain description D that only allows propositions of the form a causes f if p1, ..., pn and observation O about only the initial state: Define when (D, O) entails a query Q.
Hint: You may define initial states corresponding to a given O, and transition function(s) corresponding to a given D, and then use them to define when (D, O) entails a query Q.
2. Show your attempt at proving R1, R2 and R3.
3. Prove that 3-SAT is NP-complete.
Prove in detail R3 and R5. (The slides give you the sketch. You need to prove that the transformation from 3SAT to the problems R3 and R5 is such that: (i) F is satisfiable iff deciding (D,O), as constructed, is consistent. (ii) F is satisfiable iff there is a plan with respect to D, O, and the goal, as constructed. )
In the maintainability slides, a direct algorithm using s_i, s_i' etc. is given. In a subsequent slide hints about how to use counters to develop a new direct algorithm is given. (This algorithm is available in the paper on this topic.) Write down this algorithm. Illustrate how the direct algorithm using counters works on the example that I illustrated in the class.
Described in slide 8 of Set 3-1. The reference in the 4th bullet is to slide 2 of that set.
Some solution and additional hints.