О трудностях решения специальных систем булевых уравнений Сафарян, Ашот Араратович

brief description

Сафарян, Ашот Араратович.
О трудностях решения специальных систем булевых уравнений : диссертация ... кандидата физико-математических наук : 01.01.09. - Москва, 1985. - 89 с. : ил.
Оглавление диссертациикандидат физико-математических наук Сафарян, Ашот Араратович
ВВЕДЕНИЕ.
ГЛАВА I. СИСТЕМЫ ТЕСТОВЫХ УРАВНЕНИЙ.
§ I.1. Основные обозначения и определения
§ 1.2. Труднорешаемость систем тестовых уравнений.
§ 1.3. Сложность произведения левых частей i :" тестовых уравнений
§ 1.4. Полиномиальный алгоритм для решения задачи декомпозиции систем тестовых уравнений на оптимальные блоки из двух уравнений.
§ 1.5. Труднорешаемо сть задачи декомпозиции систем тестовых уравнений на блоки минимальной сложности, состоящие из трех уравнений.
ГЛАВА 2. К0НЕЧН03НАЧНЫЕ СИСТЕМЫ БУЛЕВЫХ УРАВНЕНИЙ
§ 2.1. Конечнозначные системы уравнений. Труднорешаемо сть задачи о декомпозиции двухзначных систем на оптимальные блоки из трех уравнений
§ 2.2. Примеры двухзначных систем уравнений, на которых задача декомпозиции на оптимальные 3 -блоки является трудноре-шаеюй
§ 2.3. Общий случай конечнозначных систем
ГЛАВА 3. ИССЛЕДОВАНИЕ СИСТЕМ ИЗ ШМЕТ1ШЕСКИХ И МОНОТОННЫХ ШЖВДЙ. СИСТЕМЫ НЕЯЪСОНО
ВСКИХ УРАВНЕНИЙ.
§ 3.1. Системы из монотонных функций.
§ 3.2. Системы из симметрических функций
§ 3.3. О сложности произведения левых частей нельсонов ских уравнений.
§ 3.4. Исследование задачи о декомпозиции нельсоновских систем на оптимальные
5 -блоки.