On generic NP-completeness of the problem of Boolean circuits satisfiability | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2020. № 47. DOI: 10.17223/20710410/47/8

A generic approach to algorithmic problems was proposed by Kapovich, Myasnikov, Schupp, and Shpilrain in 2003. Within the framework of this approach, the algorithmic problem is considered not on the whole set of inputs, but on a certain subset of "almost all" inputs. The concept of “almost everything” is formalized by introducing a natural measure on a set of input data. In 2017, A.N. Rybalov introduced the concept of polynomial generic reducibility of algorithmic problems, which preserves the solvability property of the problem for almost all inputs and has the transitivity property, and proved that the classical satisfiability problem for Boolean formulas is complete with respect to this reducibility in the generic analogue of the class NP . In this case, Boolean formulas were represented as binary marked up trees. In this paper, we prove the generic NP-completeness of the satisfiability problem for Boolean circuits.