Негативный результат

Теорема. Для любого e > 0 существование приближенного полиномиального алгоритма A с гарантированной точностью R_A = – e влечет P = NP.

Доказательство. Пусть такой алгоритм А существует. Покажем, как с его помощью можно решить точно одну из NP-полных задач, а именно задачу о разбиении. Дано n неотрицательных чисел a ₁,…, a_n. Можно ли разбить их на два подмножества так, чтобы сумма чисел в каждом подмножестве равнялась ? Рассмотрим задачу упаковки в контейнеры с весами предметов w_i = a_i / C, i = 1,…, n. Если их можно упаковать в два контейнера, ответ в задаче о разбиении — «ДА». Применим алгоритм А к задаче о контейнерах. Если OPT = 2, то алгоритм А тоже дает 2, иначе R_A ³ , то есть алгоритм А точный.