First intractability theorem

Theorem 3 (First Intractability Theorem). The problem of determining whether a proposition is necessarily true in a nonmonotonic plan whose action representation is sufficiently strong to represent conditional actions is NP-hard. 

---