19. Понятие о труднорешаемых , np, p и np-полных задачах. Взаимоотношение классов p, np и np-полных задач.

Широкое распространение получило соглашение о том, что задача не считается эффективно решаемой до тех пор, пока для нее не будет получен полиномиальный алгоритм. В связи с этим вводят термин труднорешаемой задачи, если для нее не существует полиномиального алгоритма.

Аббревиатура NP происходит от английских слов nondeterministic (N) и polinomial (P) и означает класс всех задач распознавания, которые могут быть решены НДВУ за полиномиальное время. В отличие от этих задач класс задач, полиномиально разрешимых на детерминированной одноленточной машине Тьюринга (ДМТ), стали называть классом P (от слова polinomial).

После того как было введено понятие класса задач NP, было доказано, что многие хорошо известные комбинаторные задачи, будучи сформулированы как задачи распознавания, оказываются эквивалентными по трудности задаче о выполнимости. Этот класс эквивалентности, состоящий из “самых трудных” задач, принадлежащих к классу NP, получил название класса NP- полных задач. Иногда его называют классом универсальных задач, которые упрощенно понимают как задачи, для которых не найдены полиномиальные алгоритмы. Однако и не доказано, что таких алгоритмов вообще не существует.