Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2020, Number 47, Pages 101–107
DOI: https://doi.org/10.17223/20710410/47/8
(Mi pdm697)
 

This article is cited in 5 scientific papers (total in 5 papers)

Mathematical Backgrounds of Informatics and Programming

On generic NP-completeness of the problem of Boolean circuits satisfiability

A. N. Rybalov

Sobolev Institute of Mathematics, Omsk, Russia
Full-text PDF (635 kB) Citations (5)
References:
Abstract: 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 <i $; $x_i = \neg x_j $ 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 $\prod\limits_{m = 1}^{n} (1 + 2 (m-1)^2 + 2(m-1) )$.
Keywords: Boolean circuit, generic complexity, Boolean satisfiability problem, NP-completeness.
Funding agency Grant number
Russian Science Foundation 18-71-10028
Bibliographic databases:
Document Type: Article
UDC: 510.52
Language: Russian
Citation: A. N. Rybalov, “On generic NP-completeness of the problem of Boolean circuits satisfiability”, Prikl. Diskr. Mat., 2020, no. 47, 101–107
Citation in format AMSBIB
\Bibitem{Ryb20}
\by A.~N.~Rybalov
\paper On generic NP-completeness of~the~problem of~Boolean~circuits satisfiability
\jour Prikl. Diskr. Mat.
\yr 2020
\issue 47
\pages 101--107
\mathnet{http://mi.mathnet.ru/pdm697}
\crossref{https://doi.org/10.17223/20710410/47/8}
Linking options:
  • https://www.mathnet.ru/eng/pdm697
  • https://www.mathnet.ru/eng/pdm/y2020/i1/p101
  • This publication is cited in the following 5 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:190
    Full-text PDF :42
    References:21
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024