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

Клас складності NP (Шаблон:Lang-en) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що $𝒫\subseteq 𝒩𝒫$.

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

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

Властивості

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

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

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

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

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

  ${\cup }_F{E}_i={\cup }_G{E}_i$

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

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

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

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

  $\sum _{i\in I_1}{y}_i=\sum _{i\in I_2}{y}_i.$

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

Див. також

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

Джерела

• Шаблон:Cinderella Book
• Шаблон:Роджерс.Теорія рекурсивних функцій