This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.
| Published in | American Journal of Mathematical and Computer Modelling (Volume 11, Issue 1) |
| DOI | 10.11648/j.ajmcm.20261101.14 |
| Page(s) | 39-54 |
| Creative Commons |
This is an Open Access article, distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution and reproduction in any medium or format, provided the original work is properly cited. |
| Copyright |
Copyright © The Author(s), 2026. Published by Science Publishing Group |
Special Decomposition, Boolean Satisfiability, Equivalence of Problems
| [1] | Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H. The complexity of satisfiability problems: Refining Schaefer’s theorem. J. Comput. Syst. Sci. 75(4), 245–254 (2009). |
| [2] | Sanjeev Arora, Boaz Barak, Computational Complexity: A Modern Approach 2007. |
| [3] | Armin Biere, Marijn Heule, Hans van Maaren and Toby Walsh, Handbook of Satisfiability, IOS Press, 2008. |
| [4] | Cook, S. A., The complexity of theorem - proving procedures. In Conference Record of Third Annual ACM Symposium on Theory of Computing (1971), 151–158. |
| [5] | Yves Crama, Peter L. Hammer, Boolean Functions. Theory, Algorithms, and Applications, 2011. |
| [6] | Peter G´acs, Boston University and L´aszl´o Lov´asz, Yale University, Complexity of Algorithms Lecture Notes, Spring 1999. |
| [7] | Michael R. Garey, David S. Johnson, and Larry J. Stockmeyer. Some simplified NP-complete graph problems. Theoretical Computer Science 1(3): 237–267, 1976. |
| [8] | S. A. Gizunov and V. A. Nosov, Recognition complexity for Sheffer classes, Mosc. Univ. Math. Bull. 51, no. 4, pp. 86–88, 1996. UDC 519.716. |
| [9] |
A. Horn, On sentences which are true of direct unions of algebras. Journal of Symbolic Logic. 16(1): 14–21, 1951.
https://doi.org/10.2307/2268661 JSTOR 2268661. S2CID 42534337. |
| [10] | Thomas Jech, Set Theory, The Third Millennium Edition, 2003. |
| [11] | Karp, R. M., Reducibility among combinatorial problems. In Complexity of Computer Computations (1972), R. E. Miller and J. W. Thatcher, Eds., Plenum Press, 85–103. |
| [12] | (L. A. Levin, “Universal problems of full search”, Probl. Inf. Transm., 9: 3 (1973), 265–266). |
| [13] | Stepan Margaryan, Special Coverings of Sets and Boolean Functions, American Journal of Mathematical and Computer Modeling (Volume 10, Issue 3), 84-97. |
| [14] | J. Donald Monk, Mathematical Logic. Springer-Verlag, 1976. |
| [15] | Daniel Pierre Bovet and Pierluigi Crescenzi. Introduction to the Theory of Complexity. Prentice-Hall, New York, 1993. |
| [16] | Charles C. Pinter, A Book of Set Theory, 2014. |
| [17] | E. A. Potseluevskaya, Approximation of Boolean functions to Schaefer’s classes. Journal of Mathematical Sciences, June 2012, vol 183. |
| [18] | Rogers, H., Jr.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987). |
| [19] | Kenneth H. Rosen, Discrete Mathematics and its Applications, seventh edition, 2012. |
| [20] | Thomas J. Schaefer, The complexity of Satisfiability Problems, 1978. Department of Mathematics University of California, Berkeley, California 94720. |
| [21] | Edward R. Scheinerman, Mathematics: A Discrete Introduction, Third Edition 2013. |
| [22] | Sipser Michael, Introduction to the Theory of Computation, 2012, Cengage Learning. |
APA Style
Margaryan, S. (2026). On Important Applications of Special Set Decomposition. American Journal of Mathematical and Computer Modelling, 11(1), 39-54. https://doi.org/10.11648/j.ajmcm.20261101.14
ACS Style
Margaryan, S. On Important Applications of Special Set Decomposition. Am. J. Math. Comput. Model. 2026, 11(1), 39-54. doi: 10.11648/j.ajmcm.20261101.14
Share This Article
Twitter
Linked In
Facebook
Copy
Download@article{10.11648/j.ajmcm.20261101.14,
author = {Stepan Margaryan},
title = {On Important Applications of Special Set Decomposition},
journal = {American Journal of Mathematical and Computer Modelling},
volume = {11},
number = {1},
pages = {39-54},
doi = {10.11648/j.ajmcm.20261101.14},
url = {https://doi.org/10.11648/j.ajmcm.20261101.14},
eprint = {https://article.sciencepublishinggroup.com/pdf/10.11648.j.ajmcm.20261101.14},
abstract = {This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions.},
year = {2026}
}
TY - JOUR T1 - On Important Applications of Special Set Decomposition AU - Stepan Margaryan Y1 - 2026/02/06 PY - 2026 N1 - https://doi.org/10.11648/j.ajmcm.20261101.14 DO - 10.11648/j.ajmcm.20261101.14 T2 - American Journal of Mathematical and Computer Modelling JF - American Journal of Mathematical and Computer Modelling JO - American Journal of Mathematical and Computer Modelling SP - 39 EP - 54 PB - Science Publishing Group SN - 2578-8280 UR - https://doi.org/10.11648/j.ajmcm.20261101.14 AB - This paper is devoted to the study of complexity of finding a special covering for a set, as well as to obtaining some important applications of special decomposition. We formulate the problem of existence of a special covering as a decision problem. To determine the complexity class in which this problem is located, we study the relationship between this problem and the Boolean satisfiability problem, treating them as formal languages. We prove that these problems are polynomially equivalent, which means that the problem of existence of a special covering for a set is an -complete problem. In this article we also introduce a new concept ‘Replaceable Subsets’. The properties of such subsets are used to fill in the missing elements needed to obtain a special set covering. It is proved that when searching for missing elements to fill a special covering, the order in which these elements are considered does not matter. This result is of great importance in the search for satisfiability of Boolean functions. VL - 11 IS - 1 ER -
Mkhitar Sebastatsi Educational Complex, Yerevan, Armenia
Information