FPM 2010, vol. 16, no. 7, pp. 197-204

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 $l$ ² + l log₂²(l), where $l$ is the input length.

Main page

Contents of the journal

News

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