Verifying the Validity of a Conformant Plan is co-NP-Complete

The purpose of this document is to show the complexity of verifying the validity of a deterministic conformant plan. We concentrate on a simple version of the conformant planning problem (i.e., one where there is no precondition on the actions and where all conditions are defined as sets of positive or negative facts) in order to show that the complexity does not come from solving a single such formula.