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

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

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

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

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

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

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

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


computer-science np-complete
person brad    schedule 20.11.2008    source источник
comment
У вас был шаг 2 назад (я исправил). Недостаточно свести проблему к NP-полной проблеме. Вы должны свести NP-полную проблему к вашей новой проблеме. (В противном случае вы еще не показали, что ваша проблема такая же сложная, как исходная проблема NP-complete.)   -  person cjm    schedule 21.11.2008

Ответы (2)


arrow_upward
31
arrow_downward

Теорема Кука

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

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

person ShreevatsaR    schedule 20.11.2008

arrow_upward
4
arrow_downward

Чтобы дать вам суть доказательства (которое представляет собой несколько страниц тяжелой работы Garey & Johnson Computers and Intractibility):

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

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

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

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

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

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

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

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

person David Thornley    schedule 20.11.2008