Доказательство NP-полноты задачи о 3-раскраске
Доказательство. Легко увидеть, почему задача принадлежит NP. Для заданных G и k одним из сертификатов, подтверждающих истинность ответа, является k-раскраска: за полиномиальное время можно убедиться в том, что в раскраске используется не более k цветов и никакая пара узлов, соединенных ребром, не окрашена в один цвет.
Начало сведения выглядит вполне ожидаемо. Возможно, основное достоинство 3-раскраски при кодировании булевых выражений заключается в том факте, что мы можем связать узлы графа с конкретными литералами, а соединяя узлы ребрами, можно гарантировать, что им будут назначены разные цвета; это обстоятельство позволяет связать с одним узлом истинное, а с другим — ложное значение.
С учетом сказанного мы определяем узлы и , соответствующие каждой переменной и ее отрицанию . Также определяются три «специальных узла» T, F и B (сокращения от True, False и Base).
Для начала мы соединим каждую пару узлов vi, ребром и соединим оба этих узла с Base (в результате чего образуется треугольник из vi, и Base для каждого i). Также True, False и Base соединяются в треугольник.
- В любой 3-раскраске графа G узлам vi и должны быть назначены разные цвета, и оба они должны отличаться от цвета Base.
- В любой 3-раскраске графа G узлам True, False и Base должны быть назначены все три цвета в некоторой перестановке. В дальнейшем эти три цвета будут называться цветами True, False и Base в зависимости от того, какому из узлов соответствует тот или иной цвет.
В частности, это означает, что для всех i одно из значений vi или получает цвет True, а другому достается цвет False. В оставшейся части этого построения будем считать, что переменной xi значение 1 в заданном экземпляре 3-SAT присваивается в том, и только в том случае, если узлу vi назначается цвет True.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу