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.

UDC: 519.712.2

 English version: Journal of Mathematical Sciences (New York), 2012, 183:3, 407–412

Bibliographic databases:

• 
•