P, NP, NP - полные задачи. (4)P, NP и NP-полные задачи. Задача (преобразования или распознавания) z называется полиномиальной
 Скачать 15.13 Kb.
|
|
СРС 4 Касенов Максат P, NP и NP-полные задачи. Задача (преобразования или распознавания) Z называется полиномиальной, если найдется полиномиальный алгоритм, решающий эту задачу. Если задача распознавания Z — полиномиальна, то говорят, что она принадлежит классу P, и пишут Z ∈ P. Класс P — множество всех задач распознавания, которые можно решить полиномиальным алгоритмом. Пусть Z — задача распознавания. Алгоритм C с входами z, u проверяет с параметрами c,t > 0, задачу Z, если для любого примера z ∈ Z выполняется следующее: получив на вход этот пример z, в случае z ∈ LZ для каких-то дополнительных входных данных uz , |uz | 6 c|z| t , он через конечное число шагов останавливается и выдает «да»; 2) в случае z ∈/ LZ ни для каких дополнительных входных данных u, |u| 6 c · |z| t , он не может выдать «да». Для каждого примера z ∈ LZ дополнительные входные данные uz называются сертификатом примера z, а алгоритм C называется проверкой сертификата. Класс NP Если для задачи распознавания Z найдется полиномиальный алгоритм с некоторыми параметрами c, t, c,t > 0, проверяющий эту задачу, то говорят, что она принадлежит классу NP, и пишут Z ∈ NP. Класс NP — множество всех задач распознавания, которые можно проверить полиномиальным алгоритмом. NP – Полная задача Задача распознавания Z0 называется NP-полной, если 1) Z0 ∈ NP и 2) Z0 является NP-трудной. |