Клас складності NP
Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати недетермінованими алгоритмами за поліноміальний час; тобто, недетермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що .[1]
Формальне визначення
Мова належить до класу NP (недетермінованих поліноміальних) якщо вона розпізнається недетермінованою машиною Тюрінга з поліноміальною часовою складністю .[2]
Властивості
Оскільки кожна детермінована машина Тюринга може розглядатись як недетермінована, але без вибору варіантів кроків, то клас є підмножиною . Однак до класу складності NP належить багато інших задач, належність яких до класу P не доведена.[2]
Однією з найгостріших задач математики є з'ясування вірності тотожності . Тобто, пошуку відповіді на питання, чи є правильним твердження, що будь-що, що виконує недетермінована машина Тюринга за поліноміальний час можна виконати на детермінованій машині за, можливо більший, поліноміальний час.
Приклад задач
До задач класу складності NP належать:[3]
- Розв'язність логічного виразу.
- Триколірне розфарбування графу.
- Побудова кліки з вершин на неорієнтованому графі.
- Покриття множин: нехай задане сімейство підмножин деякої множини ; необхідно знайти підсемейство із , так, що:
- Розбиття множин: за попередніх умов, але, крім того, вимагається, щоб (для довільних з ).
- Існування гамільтонового циклу на неорієнтованому графі.
- Задача пакування рюкзака: для змінних , що приймають значення 0 та 1 розв'язати рівняння:
- де та — наперед задані цілі числа.
- для загального випадку, ця задача є розв'язанням діофантового рівняння.
- Розбиття на дві частини: нехай дано чисел з , необхідно розбити на дві множини та що не перетинаються, так, щоб:
- Задача комівояжера[4].
Посилання
- ↑ Рейнгольд, Нивергельт Ю., Део Н. (1980). Комбинаторные Алгоритмы (рос.) . Москва: Мир. с. 444.
- ↑ а б 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.
- ↑ Лорьер Ж.-Л. (1991). Системы искусственного интеллекта. пер. с фр. Мир.
- ↑ Adleman, Leonard M. Molecular computation of solutions to combinatorial problems.