Algorithm for minimization of functional associated with 3-sat problem and its practical usage
V.I. Dulkeyt, R.T. Faizullin, I.G. Khnykin

Omsk F.M. Dostoevsky State University

Full text of article: Russian language.

Abstract:
One of the most challenging issues in discrete mathematics is a problem of finding a decisive set in SATISFIABILITY application. After Cook’s classical paper [5], efforts of many researchers were aimed at build-up of heuristic direct-search algorithms to solve the satisfaction of a Conjuctive Normal Form (CNF). A perspective trend is the reduction of CNF to a continuous analogue, to searching absolute minimum of the associated function. In this paper we demonstrate feasibility of choice of a special function form and propose application of the modified method of successive approximations to solve a set of nonlinear algebraic equations, which define stationary points of the function. The paper also shows that the method can be successfully applied to solve critical issues of the cryptoanalysis of nonsymmetric codes.

Key words:
undecidable problems, computability theory, complexity classes.

Citation: Dulkeyt VI, Faizullin RT, Khnykin IG. Function minimization algorithm for 3-SAT and its practical applications [In Russian]. Computer Optics 2008; 32(1): 68-73.

References:

  1. Bespalov DV, Semenov AA. About logical statements for 2-FACTORIZATION problem [In Russian]. Calculation Technologies 2002; 7(2).
  2. Faizullin,RT. On solution of nonlinear algebraic systems of hydraulics [In Russian]. Sib. Zh. Ind. Mat.1999; 2(2): 176-184.
  3. Faizullin RT, Khnykin IG, Dulkeyt VI, Salaev EV. Function minimization algorithm for 3-SAT and its practical applications [In Russian]. Chelyabinsk 2007.
  4. Khnykin IG. CNF modifications equivalent to problems of asymmetric ciphercryptoanalysis by a resolution technique [In Russian]. ITMU (Information Technologies for Modeling and Control) 2007; 8.
  5. Cook SA. The Complexity of Theorem Proving Procedures. Proceedings Third Annual ACM Symposium on Theory of Computing, May 1971.

© 2009, ИСОИ РАН
Россия, 443001, Самара, ул. Молодогвардейская, 151; электронная почта: ko@smr.ru ; тел: +7 (846) 332-56-22, факс: +7 (846 2) 332-56-20