Complexity of Algorithms for Problems in Proposition Logic

摘要

Our work under ONR sponsorship has produced results illuminating the nature ofcertain well-known polynomial time subclasses of Satisfiability. Most of these classes are interesting because they have arisen from consideration of Linear Programming concepts to formulations of Satisfiability. We have also achieved progress in the related area of the well-founded semantics for logic programming.