This article is cited in 2 papers

Large Systems

Testing the satisfiability of algebraic formulas over the field of two elements

M. N. Vyalyi<sup>abc

a</sup> Federal Research Center “Computer Science and Control” of the Russian Academy of Sciences, Moscow, Russia
^b National Research University—Higher School of Economics, Moscow, Russia
^c Moscow Institute of Physics and Technology (State University), Moscow, Russia

Abstract: We construct a probabilistic polynomial algorithm for testing the satisfiability of algebraic formulas of depth 3 over the two-elementfield, with addition as the top operation in the formulas. An algorithm with the same characteristics exists for the problem of testing whether a polynomial given by formulas of this type is identically zero (PIT problem). However, these problems and algorithms for their solution are essentially different. The probabilistic algorithm for the PIT problem is based on the Schwartz–Zippel lemma, whereas the satisfiability testing algorithm proposed in this paper is based on the Valiant–Vazirani lemma.

Keywords: satisfiability of Boolean formulas, probabilistic algorithm, algebraic formulas.

UDC: 621.391 : 519.16

Received: 18.12.2022
Revised: 12.02.2023
Accepted: 13.02.2023

DOI: 10.31857/S0555292323010059

 English version: Problems of Information Transmission, 2023, 59:1, 57–62