О распознавании сложности аппроксимации булевых функций.

О распознавании сложности аппроксимации булевых функций.

Показано, что задача распознавания существования простой аппроксимации булевой функции алгоритмически трудна.

Bibliographic Details
Main Authors:	Н.Н. Кузюрин, О.А. Прокопьев
Format:	Article
Language:	English
Published:	Ivannikov Institute for System Programming of the Russian Academy of Sciences 2004-01-01
Series:	Труды Института системного программирования РАН
Online Access:	https://www.ispras.ru/en/proceedings/isp_6_2004/isp_6_2004_41/

Similar Items

Обобщенные покрытия и их аппроксимации.
by: Н.Н. Кузюрин
Published: (2004-01-01)

О РЕАЛИЗАЦИИ УСТРОЙСТВ ПРОВЕРКИ СИММЕТРИЧНОСТИ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-11-01)

О ТАБЛИЧНОМ ЗАДАНИИ СИСТЕМ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2019-02-01)

О НЕКОТОРЫХ СВОЙСТВАХ КОЭФФИЦИЕНТОВ ЧИСЛОВОЙ НОРМАЛЬНОЙ ФОРМЫ БУЛЕВЫХ ФУНКЦИЙ
by: М. Л. Буряков
Published: (2008-06-01)

О СИЛЬНОЙ УСТОЙЧИВОСТИ РЕШЕНИЙ ВЕКТОРНОЙ ЗАДАЧИ МИНИМИЗАЦИИ ПОРОГОВЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2019-01-01)

ИМПЛИКАТИВНЫЙ МЕТОД АНАЛИЗА ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-03-01)

РЕАЛИЗАЦИЯ ЭВРИСТИЧЕСКОГО МЕТОДА ДЕКОМПОЗИЦИИ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-11-01)

ОБ ОДНОЭЛЕМЕНТНОЙ ФУНКЦИОНАЛЬНОЙ ПОЛНОТЕ В АЛГЕБРЕ БУЛЕВЫХ ФУНКЦИЙ
by: Горюшкин, А.П., et al.
Published: (2011-12-01)

О наилучшей полиномиальной аппроксимации $(\psi,\beta)$-дифференцируемых функций в пространстве $L_2$
by: S.B. Vakarchuk
Published: (2017-06-01)

Некоторые аспекты аппроксимации и интерполяции функций искусственными нейронными сетями
by: Галкин, В.А., et al.
Published: (2022-05-01)

Полиномиальные аппроксимации некоторых функций активации нейронных сетей
by: Grigory Marshalko, et al.
Published: (2022-02-01)

ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ – ПОИСК ПОДХОДЯЩЕГО РАЗБИЕНИЯ
Published: (2018-11-01)

ДНФ-РЕАЛИЗАЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ
Published: (2018-07-01)

МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-10-01)

ОПТИМИЗАЦИЯ СКОБОЧНЫХ ПРЕДСТАВЛЕНИЙ БУЛЕВЫХ ФУНКЦИЙ С УЧЕТОМ ЭНЕРГОПОТРЕБЛЕНИЯ
Published: (2018-04-01)

ВЕРИФИКАЦИЯ ЛОГИЧЕСКИХ СХЕМ, РЕАЛИЗУЮЩИХ СИСТЕМЫ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-04-01)

МЕТОД МИНИМИЗАЦИИ СИСТЕМЫ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-10-01)

ДЕКОМПОЗИЦИЯ СИСТЕМЫ БУЛЕВЫХ ФУНКЦИЙ ПО ЗАДАННЫМ ВХОДНЫМ ФУНКЦИЯМ
Published: (2019-01-01)

О существовании тригонометрических аппроксимаций Эрмита – Якоби и нелинейных аппроксимаций Эрмита – Чебышева
by: Александр Павлович Старовойтов, et al.
Published: (2023-07-01)

МИНИМИЗАЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ДИЗЪЮНКТИВНЫХ НОРМАЛЬНЫХ ФОРМ
Published: (2018-12-01)

РАЗВИТИЕ ТАБЛИЧНОГО МЕТОДА ДЕКОМПОЗИЦИИ СИСТЕМЫ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ
Published: (2019-01-01)

Неравенства типа Джексона для рельефной и полиномиальной аппроксимации гармонических функций
by: V.F. Babenko, et al.
Published: (2013-08-01)

ДЕКОМПОЗИЦИЯ ЧАСТИЧНЫХ БУЛЕВЫХ ФУНКЦИЙ - ПРОВЕРКА НА РАЗДЕЛИМОСТЬ ПО ЗАДАННОМУ РАЗБИЕНИЮ
Published: (2018-11-01)

СРАВНЕНИЕ СХЕМНЫХ РЕАЛИЗАЦИЙ VHDL-МОДЕЛЕЙ, ИСПОЛЬЗУЮЩИХ ЧАСТИЧНУЮ ОПРЕДЕЛЕННОСТЬ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-12-01)

Покрытие графов циклами и быстрое восстановление оптоволоконных сетей.
by: Н.Н. Кузюрин, et al.
Published: (2004-01-01)

Вероятностный анализ различных шельфовых алгоритмов упаковки прямоугольников в полосу.
by: Н.Н. Кузюрин, et al.
Published: (2007-01-01)

Алгоритмические задачи с таблицами значений булевых полиномов.
by: М.Н. Вялый
Published: (2004-01-01)

ВЕРИФИКАЦИЯ ФУНКЦИОНАЛЬНЫХ ОПИСАНИЙ С НЕОПРЕДЕЛЕННОСТЬЮ НА ОСНОВЕ ПАРАФАЗНОГО ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ
Published: (2018-05-01)

ПРИМЕНЕНИЕ ОБЛАЧНЫХ ТЕХНОЛОГИЙ ПРИ РАСПОЗНАВАНИИ РЕЧИ
Published: (2018-02-01)

О связи полианалитических функций и функций Блоха
by: Шишкина А. В.
Published: (2005-01-01)

ПРОТОКОЛЫ КОЛЛЕКТИВНОЙ ЦИФРОВОЙ ПОДПИСИ, ОСНОВАННЫЕ НА СЛОЖНОСТИ РЕШЕНИЯ ДВУХ ТРУДНЫХ ЗАДАЧ
by: Е. С. Дернова, et al.
Published: (2008-06-01)

ИССЛЕДОВАНИЕ МЕТОДА S-АППРОКСИМАЦИИ ДЛЯ РАЗЛИЧНЫХ ТИПОВ РЕЛЬЕФА ЗЕМНОЙ ПОВЕРХНОСТИ
by: И. А. Керимов, et al.
Published: (2018-12-01)

О применении одного класса интегральных штрафных функций при решении вариационных задач
by: Т.В. Саженкова, et al.
Published: (2018-03-01)

ДЕКОМПОЗИЦИЯ СИСТЕМ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ ПО ИХ ЗАДАНИЮ В ВИДЕ КОМПАКТНЫХ ТАБЛИЦ
Published: (2019-02-01)

Генетические алгоритмы в задаче поиска часто встречающихся комбинаций.
by: Н.Н. Кузюрин, et al.
Published: (2004-01-01)

О гладкой аппроксимации вероятностных критериев в задачах стохастического программирования
by: Vitaliy Romanovich Sobol, et al.
Published: (2020-02-01)

НОВЫЕ СВЕДЕНИЯ О ЖЕЛЕЗНОМ ЧЕКАНЕ ИЗ НЕКРОПОЛЯ НОВОТРОИЦКОЕ-I
by: Н.Н. Головченко, et al.
Published: (2022-07-01)

Эффективные алгоритмы и их программные реализации.
by: Н.Н. Кузюрин, et al.
Published: (2000-01-01)

Об особенностях применения методов обфускации программ для информационной защиты микроэлектронных схем.
by: Н.П. Варновский, et al.
Published: (2006-01-01)

О поэтической функции языка
Published: (1998-12-01)