Geodesic
Approximation of Boolean functions to Schaefer's classes
Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 7, pp. 197-204 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

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. 
@article{FPM_2010_16_7_a8,
     author = {E. A. Potseluevskaya},
     title = {Approximation of {Boolean} functions to {Schaefer's} classes},
     journal = {Fundamentalʹna\^a i prikladna\^a matematika},
     pages = {197--204},
     year = {2010},
     volume = {16},
     number = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/FPM_2010_16_7_a8/}
}
TY  - JOUR
AU  - E. A. Potseluevskaya
TI  - Approximation of Boolean functions to Schaefer's classes
JO  - Fundamentalʹnaâ i prikladnaâ matematika
PY  - 2010
SP  - 197
EP  - 204
VL  - 16
IS  - 7
UR  - http://geodesic.mathdoc.fr/item/FPM_2010_16_7_a8/
LA  - ru
ID  - FPM_2010_16_7_a8
ER  - 
%0 Journal Article
%A E. A. Potseluevskaya
%T Approximation of Boolean functions to Schaefer's classes
%J Fundamentalʹnaâ i prikladnaâ matematika
%D 2010
%P 197-204
%V 16
%N 7
%U http://geodesic.mathdoc.fr/item/FPM_2010_16_7_a8/
%G ru
%F FPM_2010_16_7_a8
E. A. Potseluevskaya. Approximation of Boolean functions to Schaefer's classes. Fundamentalʹnaâ i prikladnaâ matematika, Tome 16 (2010) no. 7, pp. 197-204. http://geodesic.mathdoc.fr/item/FPM_2010_16_7_a8/

[1] Gizunov S. A., Nosov V. A., “Slozhnost raspoznavaniya klassov Shefera”, Vestn. Mosk. un-ta. Ser. 1. Matematika, mekhanika, 1996, no. 4, 7–12 | MR | Zbl

[2] Schaefer T. J., “The complexity of satisfiability problems”, Proc. of the 10th Symp. on Theory of Computing, STOC'78 (San Diego, California, USA, 1978), ACM Press, New York, 1978, 216–226 | MR | Zbl