2P or 2NP

[snyders]

В супермаркете подумал: Все таки P vs NP слишком фундаментальный вопрос, чтобы иметь простой Да/Нет ответ. Скорее это из серии проблем, о которых наши представления колеблятся с периодом 200-500 лет. Типа вопроса о природе света и вопроса из каких частичек устроена материя.

Comments

[dtim.livejournal.com]

Но, в отличие от природы света, отыскание полиномиального алгоритма для какой-нибудь SAT однозначно закрыло бы вопрос. Или нет?

[snyders.livejournal.com]

Если, я правильно понимаю, мы про довольно короткие программы не в состоянии сказать правильно они работают или нет (несколко миллионов строк). Представим себе, что нам дали алгоритм размером n^50 строк и временем n^100 -- сможем мы проверить решает он SAT или нет?