NP (складність)

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

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

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

Властивості

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

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

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

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

• Розв'язність логічного виразу.
• Триколірне розфарбування графу.
• Побудова кліки з ${\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}.}$

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

Див. також

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

Примітки

1. Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.) . Москва: Мир. с. 444.
2. John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2001). Introduction to Automata Theory, Languages and Computation (англ.) (вид. 2). Addison-Wesley. с. 419. ISBN .
3. Лорьер Ж.-Л. (1991). Системы искусственного интеллекта. пер. с фр. Мир.
4. Adleman, Leonard M. Molecular computation of solutions to combinatorial problems.

Джерела

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