19
правок
Изменения
м
→Доказательство принадлежности к NPH
===Доказательство принадлежности к NPH===
Доказательство взято из книги <ref>[Ахо, Альфред, В., Хопкрофт, Джон, Ульман, Джеффри, Д. "Структуры данных и алгоритмы" — Издательский дом «Вильямс», 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>. Для всех дизъюнктов и переменных строятся подграфы, как показано на рисунках.
