THE COMPLEXITY OF MINIMUM PARTIAL TRUTH ASSIGNMENTS AND IMPLICATION IN NEGATION-FREE FORMULAS

In Artificial Intelligence there has been a great deal of interest in the tradeoff between expressiveness and tractability for various areas of symbolic reasoning. Here we present several complexity theory resu lts for two areas, wherein we restrict the application of negation. Fi rst, we consider the problem of determining a minimum satisfying assig nment for a (restricted) propositional sentence. We show that the prob lem of determining a minimum satisfying assignment for a sentence in n egation-free CNF, even with no more than two disjuncts per clause, is NP-complete. We also show that unless P = NP, no polynomial time appro ximation scheme can exist for this problem. However, the problem is in polynomial time if either each clause contains exactly one negative a nd one positive literal or we use exclusive-OR in the clauses instead of the more standard inclusive-OR. Second, the problem of determining logical implication between sentences composed solely of conjunctions and disjunctions is shown to be as difficult as that between arbitrary sentences. We also study this problem when the sentences are restrict ed to being in CNF or DNF. Determining whether a CNF sentence logicall y implies a DNF sentence is co-NP-complete, but in all other cases thi s problem is polynomial time. We argue that these results are relevant , first to areas where a least solution (in some fashion) is desired, and second, to limited deductive systems.