Geodesic
On generic NP-completeness of the problem of Boolean circuits satisfiability
Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 101-107
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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, \ldots, x_n$. Every variable $x_i$ can be either input, or defined through other variables by assigning one of the following types: $x_i = x_j \vee x_k$ or $x_j \wedge x_k$, where $j, k ; $x_i = \neg x_j $ or $x_j $, where $j . 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 $\prod\limits_{m = 1}^{n} (1 + 2 (m-1)^2 + 2(m-1) )$.
Keywords: Boolean circuit, generic complexity, Boolean satisfiability problem, NP-completeness. 
@article{PDM_2020_1_a7,
     author = {A. N. Rybalov},
     title = {On generic {NP-completeness} of~the~problem {of~Boolean~circuits} satisfiability},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {101--107},
     year = {2020},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2020_1_a7/}
}
TY  - JOUR
AU  - A. N. Rybalov
TI  - On generic NP-completeness of the problem of Boolean circuits satisfiability
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2020
SP  - 101
EP  - 107
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/PDM_2020_1_a7/
LA  - ru
ID  - PDM_2020_1_a7
ER  - 
%0 Journal Article
%A A. N. Rybalov
%T On generic NP-completeness of the problem of Boolean circuits satisfiability
%J Prikladnaâ diskretnaâ matematika
%D 2020
%P 101-107
%N 1
%U http://geodesic.mathdoc.fr/item/PDM_2020_1_a7/
%G ru
%F PDM_2020_1_a7
A. N. Rybalov. On generic NP-completeness of the problem of Boolean circuits satisfiability. Prikladnaâ diskretnaâ matematika, no. 1 (2020), pp. 101-107. http://geodesic.mathdoc.fr/item/PDM_2020_1_a7/

[1] Kapovich I., Miasnikov A., Schupp P., Shpilrain V., “Generic-case complexity, decision problems in group theory and random walks”, J. Algebra, 264:2 (2003), 665–694 | DOI | MR | Zbl

[2] Garey M., Johnson D., Computers and Intractability, Freeman Co, N. Y., 1979, 340 pp. | MR | Zbl

[3] Levin L., “Average case complete problems”, SIAM J. Computing, 15 (1987), 285–286 | DOI | MR

[4] Gurevich Y., “Average case completeness”, J. Computer System Sciences, 42 (1991), 346–398 | DOI | MR | Zbl

[5] Rybalov A., “On generic NP-completeness of the Boolean satisfiability problem”, Prikladnaya Diskretnaya Matematika, 2017, no. 36, 106–112 (in Russian) | DOI

[6] Miasnikov A., Ushakov A., “Generic case completeness”, J. Computer System Sciences, 82:8 (2016), 1268–1282 | DOI | MR | Zbl

[7] Savage J., The Complexity of Computing, John Wiley and Sons Inc., 1977, 391 pp. | MR