P vs NP
Самая известная открытая проблема информатики: можно ли так же быстро решать задачи, ответ на которые быстро проверяется (NP)? Большинство считает, что нет, но доказательства нет. Приз Института Клэя — $1 млн.
Сформулирована Стивеном Куком в 1971 году. Если бы P = NP, рухнула бы вся криптография (RSA и AES опираются на предположения о вычислительной трудности). NP-полные задачи (коммивояжёр, SAT, рюкзак): быстро решить одну — значит быстро решить все. Практический вывод: мы признаём, что часть задач «трудна», и пользуемся эвристиками и приближениями (имитация отжига, генетические алгоритмы, LP-релаксация). Квантовые вычисления границу не сдвигают — BQP это другой класс сложности.