P и NP: насколько трудна задача?

Коротко: Классификация задач: P — те, что решаются быстро; для NP предложенное решение можно быстро проверить, а можно ли его так же быстро найти — открытый вопрос.

Подробнее: Теория сложности спрашивает, насколько сильно растут усилия с размером входных данных. «Быстро» здесь означает: не хуже полиномиального, то есть примерно n², n³ (n — размер входа). Усилие вроде 2ⁿ («экспоненциальное») растёт так сильно, что даже средние входы становятся практически неразрешимыми.

Подробности

P: быстро решаемые

P (полиномиальное время…

См. также: О-нотация, динамическое программирование, жадные алгоритмы