О распознавании сложности аппроксимации булевых функций. - Н.Н. Кузюрин; О.А. Прокопьев (Труды Института системного программирования РАН, 2004)
Показано, что задача распознавания существования простой аппроксимации булевой функции алгоритмически трудна.