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 log22(l), where l is the input length.

Main page Contents of the journal News Search

Location: http://mech.math.msu.su/~fpm/eng/k10/k107/k10709h.htm
Last modified: October 21, 2011