19
правок
Изменения
→Доказательство принадлежности к NPH
===Доказательство принадлежности к NPH===
Доказательство взято из книги <ref>[http://www.ru "Введение в теорию автоматовАхо, языков и вычислений"Альфред, ДжВ. , Хопкрофт, РДжон, Ульман, Джеффри, Д. МотваниСтруктуры данных и алгоритмы = Data Structures and Algorithms. — Издательский дом «Вильямс», Дж2000. — С. 384. — ISBN 5-8459-0122-7 (рус.) / ISBN 0-201-00023-7 (англ. Ульман)]</ref>
Сведем задачу о выполнимости булевых формул вида 3-КНФ (3CNF SAT) к HAM. Начнем построение экземпляра HAM по булевой формуле в 3КНФ. Пусть формула имеет вид <math>E = e_1 \land e_2 \land... \land e_k</math>, где каждое <math>e_i</math> - дизъюнкт, представляющий собой сумму трех литералов, скажем, <math>e_i = (\alpha_{i1} + \alpha_{i2} + \alpha_{i3})</math>. Пусть <math>x_1, x_2, ..., x_n</math> - переменные в формуле <math>E</math>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунке 1.
