FUNDAMENTALNAYA
I PRIKLADNAYA MATEMATIKA

(FUNDAMENTAL AND APPLIED MATHEMATICS)

2010, VOLUME 16, NUMBER 7, PAGES 197-204

**Approximation of Boolean functions to Schaefer's classes**

E. A. Potseluevskaya

Abstract

View as HTML
View as gif image

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 $l2+\; l\; log$_{2}^{2}(l),
where $l$ is the
input length.

Location: http://mech.math.msu.su/~fpm/eng/k10/k107/k10709h.htm

Last modified: October 21, 2011