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

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

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

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

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

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

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

  ${\displaystyle \cup _{F}E_{i}=\cup _{G}E_{i}}$

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

  ${\displaystyle \sum a_{j}x_{j}=b}$ де ${\displaystyle a_{j}}$ та ${\displaystyle b}$ — наперед задані цілі числа.

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

• Розбиття на дві частини: нехай дано ${\displaystyle n}$ чисел ${\displaystyle y_{i}}$ з ${\displaystyle {\mathcal {N}}}$, необхідно розбити на дві множини ${\displaystyle I_{1}}$ та ${\displaystyle I_{2}}$ що не перетинаються, так, що:

  ${\displaystyle \sum _{i\in I_{1}}y_{i}=\sum _{i\in I_{2}}y_{i}.}$

• Задача комівояжера^[4].

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

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