NP-повні задачі.

Кажуть, що задача A поліноміально зводиться до задачі B, якщо рішення задачі A може бути отримано з рішення задачі B за поліноміальний час.

Задача називається NP-складною, якщо до неї за поліноміальний час зводиться будь-яка NP – задача.

Якщо NP-складна задача є NP-задачею, така задача називається NP-повною. Поняття NP-повної задачі має велике значення. Якщо для будь-якої NP-повної задачі буде знайдений поліноміальний алгоритм, це означатиме, що поліноміальний алгоритм існує для будь-якої NP-задачі, і тоді виявиться, що P = NP. Але таких алгоритмів поки що знайдено не було, і шансів на їх знаходження залишається все менше і менше.

Дуже важливим є наступний результат, що був отриманий Куком: задача про виконуваність булевого виразу є NP-повною.

NP-важкі задачі

Клас складності NP (англ. Complexity class NP) — клас складності, до якого належать задачі, що можна розв'язати не детермінованими алгоритмами за поліноміальний час; тобто, не детермінованими алгоритмами в яких завжди існує шлях успішного обчислення за поліноміальний час відносно довжини вхідного рядка; очевидно, що РÍNP.

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

Властивості

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

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

<== попередня сторінка	\|	наступна сторінка ==>
Класи P та NP	\|

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.003 сек.