6.3. Вероятностные вычисления 283
Лемма 6.3.23. Для любых двух N PO-задач, если A ≤
L
B
и A ∈ AP X, то A ≤
E
B.
Определим замыкание класса MAX SN P как множество
всех NPO задач, которые E-сводятся к некоторой задаче из
MAX SN P.
Было доказано ([KMSV99]), что замыкание класса MAX SN P
совпадает с подклассом APX , содержащим все задачи из APX ,
все решения которых ограничены полиномом от длины входа
(обозначение APX PB). В частности, следствием этого резуль-
тата явился тот факт, что любой результат о MAX SN P-
полноте автоматически транслировался в утверждение об
APX -полноте. Таким образом, задачи, полные в MAX SN P
относительно L-сводимостей, оказались полными в APX PB
относительно E-сводимостей.
Несколько позднее, с использованием еще более общего по-
нятия AP-сводимостей, удалось доказать, что замыкание клас-
са MAX SN P совпадает с APX .
В настоящее время уже нет нужды использовать класс
MAX SN P, равно как и L-сводимости, поскольку класс APX
и AP-сводимости полностью их покрывают. Однако некото-
рые традиции и ряд полученных ранее результатов застав-
ляют зачастую обращаться к этим понятиям. Кроме того, L-
сводимости бывает проще строить, чем AP -сводимости.
В заключение приведем определение AP-сводимости (appro-
ximation preserving reducibility). На сегодняшний день эти сво-
димости являются наиболее общим типом сводимостей, сохра-
няющих аппроксимации.
Определение 6.3.29. Пусть A и B — две NPO проблемы.
AP -сводимостью задачи A к задаче B (A ≤
AP
B) называется
пара функций f и g и константа α, такие что:
• Для любого входа x ∈ I
A
и для любого r > 1, f (x, r) ∈ I
B
—
вычислимо за время t
f
(|x|, r).