On k-Positive Satisfiability Problem

摘要

An algorithm for solving the satisfiability problem is presented. It isproceed that this algorithm solves 2-SAT and Horn-SAT in linear time and k-positiveSAT (in which every clause contains at most k positive literals) ill time O(F.),where F is the length of input F, n is the number of atoms occurring in F, and k isthe greatest real number satisfying the equation x = 2-. Compared with previousresults, this nontrivial upper bound on time complexity could only be obtained fork-SAT, which is a subproblem of k-positive SAT.