4.6. Изучение задач типа NP с помощью классов эквивалентностей

Сначала мы докажем, что задачи, имеющие различные условия, но относящиеся к классу на самом деле эквивалентны.

Приводимые ниже определения позволят в первую очередь уточнить, что мы понимаем под эквивалентными задачами.

Определение 1. Задача сводится к задаче тогда и только тогда, когда для всякого решения задачи существует функция которую можно вычислить полиномиально и которая является решением задачи

Тогда является частным случаем и можно записать:

Это, кроме того, означает: если мы умеем решать то мы умеем решать и

Определение 2. Ьсли одновременно то мы говорим, что и эквивалентны.

Определение 3. Задача называется NP-сложной тогда и только тогда, когда к ней сводима любая задача из класса

Замечание. Утверждение, что задача является ЛФ-сложной, не обязательно означает ее принадлежность классу

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