Клас складності NP

Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що $\mathcal{P} \subseteq \mathcal{NP}$.

Формальне визначення

Мова $L$ належить до класу NP (недетермінованих поліноміальних) якщо вона розпізнається недетермінованою машиною Тюринга $M$ з поліноміальною часовою складністю $T(n)$.

Властивості

Оскільки кожна детермінована машина Тюринга може розглядатись як недетермінована але без вибору варіантів кроків, то клас $\mathcal P$ є підмножиною $\mathcal{NP}$. Однак, до класу складності NP належить багато інших задач, що не належать до класу P.

Однією з найгостріших задач математики є з'ясування вірності тотожності $\mathcal{P} = \mathcal{NP}$. Тобто, пошуку відповіді на питання, чи є вірним твердження, що будь-що, що виконує недетермінована машина Тюринга за поліноміальний час можна виконати на детермінованій машині за, можливо більший, поліноміальний час.

Приклад задач

До задач класу складності NP належать:

• Розв'язність логічного виразу.
• Три-кольорове розфарбування графу.
• Побудова кліки з $k$ вершин на неорієнтованому графі.
• Покриття множин: нехай задане сімейство $F$ підмножин $E_i$ деякої множини $E$; необхідно знайти підсемейство $G$ із $F$, так, що:

  $\cup_F E_i = \cup_G E_i$

• Розбиття множин: за попередніх умов, але, крім того, вимагається, щоб $E_i \cap E_j = \emptyset$ (для довільних $E_i, E_j$ з $G$).
• Існування гамільтонового циклу на неорієнтованому графі.
• Задача пакування рюкзака: для змінних $x_i$, що приймають значення 0 та 1 розв'язати рівняння:

  $\sum a_j x_j = b$ де $a_j$ та $b$ — наперед задані цілі числа.

  для загального випадку, ця задача є розв'язанням діофантова рівняння.

• Розбиття на дві частини: нехай дано $n$ чисел $y_i$ з $\mathcal N$, необхідно розбити на дві множини $I_1$ та $I_2$ що не перетинаються, так, щоб:

  $\sum_{i\in I_1} y_i = \sum_{i \in I_2} y_i.$

• Задача комівояжера.

Дивіться також

• Клас складності P
• NP-повна задача
• PCP теорема