Доказательство, что P <= NP
Как большинство людей знает, P =, NP бездоказателен и кажется маловероятным быть верным. Доказательство доказало бы что P <= NP и NP <= P. Только один из тех тверд, все же.
P <= NP почти по определению верен. На самом деле это - единственный способ, которым я знаю, как заявить что P <= NP. Это просто интуитивно. Как Вы доказали бы что P <= NP?
4 ответа
Думаю, вы по существу ответили на свой вопрос в комментариях: проблема, которая удовлетворяет определению P , также удовлетворяет определению NP .
Цитата из Википедии:
Все проблемы в P [находятся в NP] (Поскольку, имея сертификат для проблемы в P, мы можем игнорировать сертификат и просто решить проблему за полиномиальное время. В качестве альтернативы, обратите внимание, что Детерминированная машина Тьюринга также банально является недетерминированной машиной Тьюринга, которая просто случайно не использует никакого недетерминизма.)
Сертификат, на который она ссылается, является полиномиальной проверкой решения; как вы говорите, вы можете решить задачу в P за полиномиальное время и, следовательно, у вас будет решение, которое было проверено за полиномиальное время и, следовательно, находится в NP .
Ответ Джои Адамса - второе объяснение с точки зрения разрешимости (недетерминированных машин Тьюринга). См. Статью в Википедии для получения более подробного объяснения этого определения NP .
Я думаю, что вы должны здесь отметить, что тот факт, что доказательство тривиально просто, не означает, что это не доказательство. «По определению» - вполне допустимый логический шаг.
Недетерминированный компьютер может просто не ссылаться на свою недетерминированность и вести себя как детерминированный, поэтому он может решать задачи P за полиномиальное время. Это лучший ответ, который я могу придумать.
Каждая проблема в NP решается недетерминированной машиной Тьюринга [за полиномиальное время]. (по определению *)
Каждая проблема в P решается детерминированной машиной Тьюринга [за полиномиальное время]. (по определению)
Каждая детерминированная машина Тьюринга также является недетерминированной машиной Тьюринга. (очевидно)
Следовательно, каждая проблема в P решается недетерминированной машиной Тьюринга [за полиномиальное время].
Следовательно, каждая проблема в P является проблемой в NP. Следовательно, P ⊆ NP.
* Давайте прочитаем статью в Википедии о NP:
В эквивалентном формальном определении NP - это набор задач принятия решений, решаемых за полиномиальное время с помощью недетерминированной машины Тьюринга.
Нет необходимости вводить этот материал о полиномиальной проверке в такое простое рассуждение.
Недетерминированный компьютер, который решает задачу (NP) за полиномиальное время, также решает задачу P за полиномиальное время.
Если мы рассмотрим воображаемый подход машины Тьюринга, который может пройти несколько путей для решения задачи NP за полиномиальное время, этого поведения должно быть достаточно, чтобы решить проблему P за время P. Детерминированные машины Тьюринга - это случай простых (реальных) недетерминированных машин.