Volume 27, No 1, 2020, P. 110-126

UDC 519.97
N. G. Parvatov
Finding the subsets of variables of a partial Boolean function which are sufficient for its implementation in the classes defined by predicates

Abstract:
Given a class $K$ of partial Boolean functions and a partial Boolean function $f$ of $n$ variables, a subset $U$ of its variables is called sufficient for the implementation of $f$ in $K$ if there exists an extension of $f$ in $K$ with arguments in $U$. We consider the problem of recognizing all subsets sufficient for the implementation of $f$ in $K$. For some classes defined by relations, we propose the algorithms of solving this problem with complexity of $O(2^{n}n^2)$ bit operations. In particular, we present some algorithms of this complexity for the class $P_2^\ast$ of all partial Boolean functions and the class $M_2^\ast$ of all monotone partial Boolean functions. The proposed algorithms use the Walsh–Hadamard and Möbius transforms.
Bibliogr. 21.

Keywords: partial Boolean function, sufficient subset of variables, Walsh–Hadamard transform, Möbius transform.

DOI: 10.33048/daio.2020.27.664

Nikolay G. Parvatov ¹
1. Tomsk State University,
36 Lenin Avenue, 634050 Tomsk, Russia
e-mail: ngparvatov@yandex.ru

Received June 20, 2019
Revised November 5, 2019
Accepted November 27, 2019

References

[1] O. I. Golubeva, Construction of permissible functions and their application for fault tolerance, in Proc. Int. Sib. Conf. Control and Communications (Tomsk, Russia, Apr. 18–20, 2019) (TUSUR, Tomsk, 2019), pp. 1–5.

[2] A. A. Voronenko, On a decomposition method for recognizing membership in invariant classes, Diskretn. Mat. 14 (4), 110–116 (2002) [Discrete Math. Appl. 12 (6), 607–614 (2002)].

[3] S. N. Selezneva, Constructing polynomials for functions over residue rings modulo a composite number in linear time, in Lecture Notes in Computer Science, Vol. 7353 (Springer, Heidelberg, 2012), pp. 303–312.

[4] V. B. Alekseev and N. R. Emel’yanov, A method for constructing fast algorithms in k-valued logic, Mat. Zametki 38 (1), 148–156, 171 (1985) [Math. Notes 38 (1), 595–600 (1985)].

[5] V. B. Alekseev, Stepwise bilinear algorithms and recognition of completeness in $k$-valued logics, Izv. Vyssh. Uchebn. Zaved. Mat., No. 7, 19–27 (1988) [Soviet Math. (Izv. VUZ) 32 (7), 31–42 (1988)].

[6] V. B. Alekseev, Logical semirings and their usage for construction of quick algorithms, Vestn. Mosk. Univ., Ser. I: Mat. Mekh., No. 1, 22–29 (1997) [Moscow Univ. Math. Bull. 52 (1), 22–28 (1997)].

[7] N. G. Parvatov, Generating sufficient sets for partial Boolean functions, Vestn. Tomsk. Gos. Univ., Suppl., No. 23, 44–48 (2007).

[8] V. N. Sachkov, Combinatorial Methods of Discrete Mathematics (Nauka, Moscow, 1977).

[9] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes (North-Holland, Amsterdam, 1977; Svyaz’, Moscow, 1979).

[10] S. K. Rushforth, Fast Fourier–Hadamard decoding of orthogonal codes, Inform. Control 15 (1), 33–37 (1969).

[11] A. A. Malyutin, Fast correlation decoding of some subsets of words of the first-order Reed–Muller code, Diskretn. Mat. 2 (2), 155–158 (1990) [Discrete Math. Appl. 2 (2), 155–158 (1992)].

[12] Yu. D. Karyakin, Fast correlation decoding of Reed–Muller codes, Probl. Peredachi Inform. 23 (2), 40–49 (1987).

[13] N. N. Tokareva, Generalizations of bent functions: A survey of publications, Diskretn. Anal. Issled. Oper. 17 (1), 34–64, 99 (2010) [J. Appl. Ind. Math. 5 (1), 110–129 (2011)].

[14] L. Weisner, Abstract theory of inversion of finite series, Trans. Amer. Math. Soc. 38, 474–484 (1935).

[15] P. Hall, The Eulerian functions of a group, Q. J. Math. 7, 134–151 (1936).

[16] G. C. Rota, On the foundations of combinatorial theory. I. Theory of Möbius functions, Z. Wahrscheinlichkeitstheorie und Verw. Gebiete. 2, 340–368 (1964).

[17] R. P. Stanley, Enumerative Combinatorics, Vol. 1 (Camb. Univ. Press, Cambridge, 1997).

[18] N. G. Parvatov, On recognizing of properties of discrete functions by Boolean circuits, Vestn. Tomsk. Gos. Univ., Suppl., No. 14, 233–236 (2005).

[19] A. Schönhage and V. Straßen, Schnelle multiplikation großer zahlen, Computing 7, 281–292 (1971).

[20] M. Fürer, Faster integer multiplication, In Proc. 39th Annual ACM Symp. Theory of Computing, San Diego, CA, USA, June 11–13, 2007 (ACM, New York, 2007), pp. 57–66.

[21] A. De, C. Saha, P. Kurur, and R. Saptharishi, Fast integer multiplication using modular arithmetic, in Proc. 40th Annual ACM Symp. Theory of Computing, Victoria, Canada, May 17–20, 2008 (ACM, New York, 2008), pp. 499–506 [SIAM J. Comput. 42 (2), 685–699 (2013)].