Как первые NP-полные проблемы оказались NP-полными?

Из записи wikipedia на NP-Complete:

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

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

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

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

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

Ответ 1

Теорема о кулинарии

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

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

Ответ 2

Чтобы дать вам сущность доказательства (что несколько страниц трудных в Garey and Johnson Computers и нецелесообразности):

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

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

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

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

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

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

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

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