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

Мова ${\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-теорема