|
Fundamentalnaya i Prikladnaya Matematika, 2010, Volume 16, Issue 7, Pages 197–204
(Mi fpm1370)
|
|
|
|
Approximation of Boolean functions to Schaefer's classes
E. A. Potseluevskaya M. V. Lomonosov Moscow State University
Abstract:
We consider an algorithm for transferring Boolean functions to function classes for which the generalized satisfiability problem is solvable in polynomial time (Schaefer's classes). For the case where an initial function is represented as a truth-table, it is proved that the complexity of the algorithm is $l^2+l\log_2^2(l)$, where $l$ is the input length.
Citation:
E. A. Potseluevskaya, “Approximation of Boolean functions to Schaefer's classes”, Fundam. Prikl. Mat., 16:7 (2010), 197–204; J. Math. Sci., 183:3 (2012), 407–412
Linking options:
https://www.mathnet.ru/eng/fpm1370 https://www.mathnet.ru/eng/fpm/v16/i7/p197
|
|