Recognition of zero bits of 3-sat problem by applying linear algebra’s methods

Y.Y. Ogorodnikov, R.T. Faizullin

Full text of article: Russian language.

Abstract**:**

The paper presents two heuristic methods of recognizing zero bits satisfiability problem. The first is based on the reduction of the satisfiability problem to an equivalent problem of minimizing a continuous smooth function by method of successive approximations, extended by changing the order of calculation of variables. Another way is to reduce to a system of linear algebraic equations with symmetric diagonally dominant matrix.

Key words:

satisfiability, method of successive approximations, the order of calculation of variables, diagonal methods, factorization.

References:

**Cook, S.**The complexity of theorem-proving procedures / S. Cook // Proceedings of the Third Annual ACM Symposium on Theory of Computing. – 1971. – P. 151-158.**Dulkeit, V.I.**Reduction of factorization, discrete logarithm and elliptic curve logarithm problems to solving associated satisfiability problems / V.I.Dulkeit // Computer Optics. – 2010. – V.34(1). – P. 118-123. – ISSN 0134-2452. – (In Russian).

**Menezes, A.**Handbook of applied cryptography / A. Menezes, P. van Oorschot, S. Vanstone. – CRC Press, 2001. – 780 p.

**Patsakis, C.**RSA private key reconstruction from random bits using SAT solvers [Electronic resource]. – Mode of access: https://eprint.iacr.org/2013/026. – Access date: 01.03.2013.

**Martin, D.**A Machine Program for Theorem Proving / D. Martin, G. Logemann, L. Donald // Communications of the ACM. – 1962. – V. 5(7)*.*– P. 394–397. – ISSN: 0001-0782.

**Dulkeit, V.I.**Continuous approximation of SAT decision as applied to cryptographic analysis of asymmetric ciphers /V.I. Dulkeit, I.G.Hnikin, R.T.Faizullin // Computer Optics. – 2009. – V. 33(1). – P. 86–91. – ISSN 0134-2452. – (In Russian).

**Dulkeit, V.I.**A hybrid method of searching the approximate solution of 3-SAT, associated with factorization problem / V.I. Dulkeit, R.T. Faizullin, Y.Y. Ogorodnikov // Proceedings of the Institute of Mathematics and Mechanics URAN. – 2013. – V. 19(2). – P. 285-294. – ISSN: 0134-4889. – (In Russian).

- Numerical methods / A.A. Samarski, A.V. Gulin. – M.: “Fismatlit” Publisher, 1989. – 432 p. – (In Russian).

- Witold Lipski. Kombinatoryka dla programistow. – “Warszawa” Publisher, 1982.
**Faizullin, R.T.**Problems of linear algebra, correlated with the satisfiability problem / R.T. Faizullin //Applied Discrete Mathematics. – 2009. – Application № 1. – P. 90-91. – ISSN: 2071-0410. – (In Russian).

**© 2009,**Institution of Russian Academy of Sciences, Image Processing Systems Institute of RAS, Russia, 443001, Samara, Molodogvardeyskaya Street 151; e-mail: ko@smr.ru; Phones: +7 (846 2) 332-56-22, Fax: +7 (846 2) 332-56-20**IPSI RAS**