Доказательство того, что P <= NP

Question

Как большинство людей знают, P = NP не доказано и вряд ли может быть правдой. Доказательство докажет, что P <= NP и NP <= P. Но только одно из них сложно. </p>

P <= NP почти по определению верно. Фактически, это единственный способ, которым я знаю, как утверждать, что P <= NP. Это просто интуитивно понятно. Как бы вы доказали, что P <= NP? </p>

Answer 1

Каждая проблема в NP решается с помощью недетерминированной машины Тьюринга [за полиномиальное время].(по определению *)

Каждая проблема в P решается с помощью детерминированной машины Тьюринга [за полиномиальное время].(по определению)

Каждая детерминированная машина Тьюринга также является недетерминированной машиной Тьюринга.(очевидно)

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

Следовательно, каждая проблема в P является проблемой в NP.Следовательно, P ⊆ NP.

---

* Давайте прочитаем статью Википедии на NP:

В эквивалентном формальном определении NP - это набор задач для решенияразрешима за полиномиальное время недетерминированной машиной Тьюринга.

Нет необходимости вводить этот материал о полиномиальной проверке в такие простые рассуждения.

Answer 2

Я думаю, что вы, по сути, ответили на свой вопрос в комментариях: проблема, которая удовлетворяет определению P, также удовлетворяет определению NP.

Цитировать Википедию:

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

Сертификат, на который он ссылается, является проверкой решения за полиномиальное время; как вы говорите, вы можете решить проблему в P за полиномиальное время, и поэтому у вас будет решение, которое было проверено за полиномиальное время и поэтому находится в NP.

Ответ Джои Адамса является вторым объяснением с точки зрения разрешимости (не) детерминированными машинами Тьюринга. См. статью в Википедии для более подробного объяснения этого определения NP.

Я думаю, что вы должны здесь отметить, что факт, что доказательство тривиально просто, не означает, что это не доказательство. «По определению» - вполне допустимый логический шаг.

Answer 3

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

Answer 4

Недетерминированный компьютер, который решает (NP) задачу за полиномиальное время, также решал бы проблему P. за полиномиальное время.

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