как были показаны первые NP-полные задачи как NP-полные?

Question

Из записи в Википедии о NP-Complete:

" Самый простой способ доказать, что какая-то новая проблема является NP-полной, - это сначала доказать, что она есть в NP, а затем свести к ней некоторую известную NP-полную проблему "

Я почти уверен, что понимаю это: если у меня есть проблема, я могу показать, что она NP-Complete, если я:

<Ол>

показать, что он находится в NP (решение проблема может быть проверена в полиномиальное время на недетерминированная машина Тьюринга)

Покажите, что проблема, уже известная как NP-Complete, может быть «сводится» к новой проблеме

Итак, мой вопрос: как «доказано», что первые NP-полные задачи были NP-полными? Когда-то набор известных NP-полных задач должен был быть нулевым, и это сделало бы невозможным использование шага 2 в вышеописанном процессе.

Это заставляет меня думать, что есть другой метод доказательства, который я не знаю. Либо это, либо, возможно, все NP-полное свойство «предполагается» для определенных задач из-за отсутствия известного решения за полиномиальное время. (на самом деле, написав это, я не удивлюсь, если это так, но я бы хотел получить обратную связь с гуру в любом случае).

Answer 1

Теорема Кука

Класс NP можно определить как класс задач, разрешимых недетерминированной машиной Тьюринга за полиномиальное время. Эта теорема показывает, что SAT является NP-полным путем кодирования работы любой недетерминированной машины Тьюринга с помощью булевой формулы таким образом, что машина принимает, если и только если эта формула является SATisfiable.

С исторической точки зрения, понятие NP-полноты было введено в оригинальной статье Ричарда Карпа ( Приводимость среди комбинаторных задач ), где он определил NP-полноту, использовал теорему Кука и одним большим шагом доказал 21 задачу NP-завершенную.

Answer 2

Чтобы дать вам суть доказательства (это несколько страниц усердной работы в «em & Computers; Intractibility» Гэри и Джонсона):

Любая вычислительная проблема может быть выражена как машина Тьюринга.

Можно выразить машину Тьюринга как логическую задачу, удовлетворяющую определенным ограничениям сложности.

Поэтому, если вы можете решить логическую задачу за полиномиальное время, вы можете решить проблему машины Тьюринга за полиномиальное время.

Это (наряду с некоторыми другими соображениями) показывает, что если вы можете решить логическую задачу за полиномиальное время, вы можете решить любую проблему NP за полиномиальное время. Это определение NP-завершения, поэтому логическая задача является NP-полной и может использоваться в качестве основы для других задач.

Используемая логическая проблема называется Удовлетворенность (часто сокращается до SAT). Учитывая серию предложений вида (A или не-B или не-C) (предложения, состоящие из любого числа предложений и отрицаний предложений, связанных логическим или), существует ли присвоение истинностных значений предложениям, которое делает все условия верны?

NP-полнота является четко определенным свойством. Единственная причина, по которой вы будете сомневаться в том, что проблема является NP-полной, заключается в том, что вы думали, что можете свести к ней еще одну NP-полную проблему, но пока не смогли найти удобную проблему или получить доказательство.

Вопрос не в том, существуют ли NP-полные проблемы или как доказать, что проблема NP-полна, а в том, что это значит. Никто еще не создал алгоритм за полиномиальное время для решения NP-полной задачи, и никто не доказал, что такой алгоритм не может существовать. Независимо от того, P = NP или нет, у нас, конечно, нет хороших алгоритмов для решения любой NP-полной задачи.

Это одна из проблем тысячелетия Фонда Клэйпула, так что если вы можете найти доказательство, которое ускользает от некоторых очень ярких людей в течение нескольких лет, то для вас есть миллион долларов.