Уменьшение направленного гамильтонианского цикла на график раскраски

Question

Проблема с 3 SAT может быть уменьшена как к графическому раскраске, так и к направленной задаче гамильтонианского цикла, но есть ли цепь сокращений, которая уменьшает направленный гамильтонианский цикл на график раскраски в полиномиальное время?

Answer 1

Пусть $ q in sf {np} $ и $ q ' in sf {np text {-} ard} $. Затем, по определению, $ Q $ (многие) снижается до $ Q '$ в полиномиальное время.

Точная цепочка сокращений будет зависеть от $ sf {np text {-} hard} $ ness доказательство $ q '$. Как правило, это подтверждается цепочкой сокращений, начиная с $ mathrm {sat} $ и заканчивая $ q '$, а затем используя Кук-Левин Теорема. Таким образом, цепочка сокращений будет сокращением от $ q $ $ mathrm {sat} $, за которой следует цепочка сокращений от $ mathrm {sat} $ до $ q '$.

Обычно существует более прямое сокращение конкретных проблем (без использования Cook-levin), поскольку обычно легко найти пропозициональную формулу, непосредственно выражающую необходимое свойство (без ссылки на TMS). Например, в случае направленного Hamiltionian Path ($ mathrm {dhp} $) и раскраски графика ($ mathrm {gc} $) вы можете уменьшить:

• $ mathrm {dhp} $ to $ mathrm {sat} $,
• $ mathrm {sat} $ to $ mathrm {3sat} $,
• $ mathrm {3sat} $ to $ mathrm {gc} $.