P і NP: наскільки важка задача?

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

Докладніше: Теорія складності питає, наскільки сильно зростають зусилля з розміром вхідних даних. «Швидко» тут означає: не гірше за поліноміальне, тобто приблизно n², n³ (n — розмір входу). Зусилля на кшталт 2ⁿ («експоненційне») зростає так сильно, що навіть середні входи стають практично нерозв’язними.

Подробиці

P: швидко розв’язувані

P (поліноміальний час…

Див. також: О-нотація, динамічне програмування, жадібні алгоритми