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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Формальне визначення[ред.ред. код]

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

Властивості[ред.ред. код]

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

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

Приклад задач[ред.ред. код]

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

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

Посилання[ред.ред. код]

  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 0-201-44124-1. 
  3. Лорьер Ж.-Л. (1991). Системы искусственного интеллекта. пер. с фр. Мир. 

Дивіться також[ред.ред. код]