Клас складності 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-теорема

Джерела

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)
• Роджерс Х.. Теория рекурсивных функций и эффективная вычислимость. — М. : Мир, 1972. — 416 с.(рос.)