ISSN:
1573-7470
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
Abstract 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 results for two areas, wherein we restrict the application of negation. First, we consider the problem of determining a minimum satisfying assignment for a (restricted) propositional sentence. We show that the problem of determining a minimum satisfying assignment for a sentence in negation-free CNF, even with no more than two disjuncts per clause, is NP-complete. We also show that unlessP=NP, no polynomial time approximation scheme can exist for this problem. However, the problem is in polynomial time if either each clause contains exactly one negative and 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 restricted to being in CNF or DNF. Determining whether a CNF sentence logically implies a DNF sentence is co-NP-complete, but in all other cases this 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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02136174
Permalink