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

Question

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

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

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

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

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

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

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

Answer 1

Теорема Кука

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

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

Answer 2

Чтобы дать вам суть доказательства (это несколько страниц усердной работы в «1001 * Компьютеры и интерактивность» Гэри и Джонсона ):

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

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

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

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

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

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

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

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