[01] Anatoly D. Plotnikov, Department of Social Informatics and Safety of Information Systems, Dalh East-Ukrainian National University, Luhansk, Ukraine.

We study the non-canonical method for solving the Satisfiability problem which given by a formula in the form of the conjunctive normal form. The essence of this method consists in counting the number of tuples of Boolean variables, on which at least one clause of the given formula is false. On this basis the solution of the problem obtains in the form YES or NO without constructing tuple, when the answer is YES. It is found that if the clause in the given formula has pairwise contrary literals, then the problem can be solved efficiently. However, when in the formula there are a long chain of clauses with pairwise a non-contrary literal, the solution leads to an exponential calculations.

Satisfiability Problem, Satisfying Tuple, Disjunction, Clause, Conjunction, NP-Complete

[01] Garey M.R. and Johnson D.S. (1979) Computers and Intractability. W.H. Freeman and Company, San Francisco. [02] Papadimitriou C.H. and Steiglitz K. (1982) Combinatorial optimization: Algo¬rithms and complexity. Prentice-Hall Inc., New Jersey. [03] Cook S. (1971) The Complexity of Theorem-Proving Procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing: pp. 151–158. [04] Karp R.M. (1972) Reducibility among combinatorial problems. In Miller, Raymond E.: Thatcher, James W. Complexity of Computer Computations. Plenum. pp. 85–103. [05] Crescenzi P. and Kann V. (1997) Approximation on the Web: A Compendium of NP Optimization Problems. Proceedings of International Workshop RANDOM’97, Bologna, 11-12 July 1997, pp. 111-118. [06] Dunne P.E. (2008) An annotated list of selected NP-complete problems. COMP202, Dept. of Computer Science, University of Liverpool. [07] Levin L.A. (1973) Universal Searching Problems. Prob. Info. Transm. 9, 265-266. [08] Valiant L. (1979) The complexity of computing the permanent. Theoret. Comput. Sci., 8, pp. 189–201. [09] Papadimitriou C.H. (1994) Computational Complexity (1st ed.). Addison Wesley. Chapter 9 (NP–complete problems). pp. 181–218. [10] Jiang J.R. (2008), The theory of NP-completeness. Dept. of Computer Science and Information Engineering. National Central University, Jhongli City, Taiwan. [11] Plotnikov A.D. (2012) Heuristic algorithm for finding the maximum independent set. Cybernetics and Systems Analysis: Volume 48, Issue 5, Page 673-680. [12] Davis M., Putman H. 1960) A computing procedure for quantification theory // Journal of the ACM. 7 (3). p. 201–215. [13] Davis M., Logeman G., Loveland D. (1962) A machine program for theorem-proving // Communications of the ACM. 5 (7). p. 394–397. [14] Kullmann O. (1999) New methods for 3-SAT decision and worst-case analysis // Theoretical Computer Science. 223 (1–2). p. 1–72.