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

Question

С момента вступления в википедии на NP-Complete:

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

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

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

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

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

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

Answer 1

Cook's Theorem

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

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

Answer 2

Чтобы дать Вам суть доказательства (что несколько страниц трудно собирается в Garey & Джонсона Компьютеры и Intractibility):

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

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

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

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

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

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

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

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