Клас складності NP () — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами, в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що .
Формальне визначення
Мова належить до класу NP (недетермінованих поліноміальних) якщо вона розпізнається недетермінованою машиною Тюрінга з поліноміальною часовою складністю .
Властивості
Оскільки кожна детермінована машина Тюринга може розглядатись як недетермінована, але без вибору варіантів кроків, то клас є підмножиною . Однак до класу складності NP належить багато інших задач, належність яких до класу P не доведена.
Однією з найгостріших задач математики є з'ясування вірності тотожності . Тобто, пошуку відповіді на питання, чи є правильним твердження, що будь-що, що виконує недетермінована машина Тюринга за поліноміальний час, можна виконати на детермінованій машині за, можливо, більший поліноміальний час.
Приклад задач
До задач класу складності NP належать: Розв'язність логічного виразу. Триколірне розфарбування графу. Побудова кліки з вершин на неорієнтованому графі. Покриття множин: нехай задане сімейство підмножин деякої множини ; необхідно знайти підсемейство із , так, що:
Розбиття множин: за попередніх умов, але, крім того, вимагається, щоб (для довільних з ). Існування гамільтонового циклу на неорієнтованому графі. Задача пакування рюкзака: для змінних , що приймають значення 0 та 1 розв'язати рівняння: де та — наперед задані цілі числа. Для загального випадку ця задача є розв'язанням діофантового рівняння. Розбиття на дві частини: нехай дано чисел з , необхідно розбити на дві множини та що не перетинаються, так, що:
Задача комівояжера.
Див. також
Клас складності P NP-повна задача PCP-теорема
Примітки
Джерела