Связь между NP и Decision Pro
Государственный T/F. Если кто-то докажет P = NP, то это будет означать, что любая проблема решения может быть решена за полиномиальное время. Я думаю, что это неверно. Я прав?
1 ответ
Если P = NP, это означает, что любая проблема решения в NP может быть решена за полиномиальное время. То есть любая проблема решения, при которой ответы "да" могут быть эффективно проверены, может быть решена за полиномиальное время.
Это не то же самое, что сказать, что все проблемы решения могут быть решены за полиномиальное время. Например, некоторые проблемы с решением (например, проблема остановки) неразрешимы, а это означает, что они не могут быть решены вообще. Доказательство P = NP не меняет этого.