ON GENERIC NP-COMPLETENESS OF THE PROBLEM OF BOOLEAN CIRCUITS SATISFIABILITY

Generic-case approach to algorithmic problems was suggested by Miasnikov, Kapovich, Schupp and Shpilrain in 2003. This approach studies behavior of an algorithm on typical (almost all) inputs and ignores the rest of inputs. In 2017 A. Rybalov introduced a concept of polynomial generic reducibility of algorithmic problem that preserves the decidability property problems for almost all inputs and has the property of transitivity, and proved that the classical problem of the satisfiability of Boolean formulas is complete with respect to this reducibility in the generic analogue of class NP. Then the Boolean formulas were represented by binary labeled trees. In this paper, we prove the generic NP-completeness of the satisfiability problem for the so-called Boolean circuits. Boolean circuit is a way to represent Boolean functions, which show how the value of a Boolean function is obtained from values of variables using logical connectives. Boolean circuits are convenient models for the development of microprocessors, and are also the most important object of studying in computational complexity theory. Boolean circuit contains a finite number of variables x(1), ..., x(n). Every variable x(i) can be either input, or defined through other variables by assigning one of the fol- lowing types: x(i) = x(j) V x(k) or x(j) Lambda x(k), where j, k < i; x(i) = or x(j) , where j < i. The last variable x(n) of the circuit is called output. By the size of a Boolean circuit we mean the number of variables in it. The number of Boolean circuits of size n is Pi(n)(m=1) (1 +2(m, -1)(2) +2(m, -1)).