Jump to content

Твердость аппроксимации

(Перенаправлено с Hard на приблизительное )

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

Трудность аппроксимации дополняет изучение алгоритмов аппроксимации , доказывая для некоторых задач ограничение на факторы, с помощью которых их решение может быть эффективно аппроксимировано. Обычно такие пределы показывают коэффициент аппроксимации, за пределами которого проблема становится NP-трудной , подразумевая, что нахождение полиномиальной аппроксимации для проблемы невозможно, если только NP=P . Однако некоторая сложность результатов аппроксимации основана на других гипотезах, примечательной из которых является гипотеза об уникальных играх .

С начала 1970-х годов было известно, что многие задачи оптимизации не могут быть решены за полиномиальное время, если только P = NP , но во многих из этих задач оптимальное решение можно было эффективно аппроксимировать до определенной степени. В 1970-х годах Теофило Ф. Гонсалес и Сартадж Сахни начали исследование сложности аппроксимации, показав, что некоторые задачи оптимизации были NP-трудными даже для аппроксимации с точностью до заданного коэффициента аппроксимации . То есть для этих задач существует такой порог, что любая аппроксимация за полиномиальное время со степенью аппроксимации, превышающей этот порог, может использоваться для решения NP-полных задач за полиномиальное время. [1] В начале 1990-х годов, с развитием теории PCP , стало ясно, что многие другие задачи аппроксимации трудно аппроксимировать и что (если только P = NP) многие известные алгоритмы аппроксимации достигают наилучшего возможного коэффициента аппроксимации.

Теория жесткости аппроксимации занимается изучением порога аппроксимации таких задач.

Пример NP-сложной задачи оптимизации, которую трудно аппроксимировать, см. в set Cover .

См. также

[ редактировать ]
  1. ^ Сахни, Сартадж ; Гонсалес, Теофило (1976), « P Задачи -полной аппроксимации», Journal of the ACM , 23 (3): 555–565, doi : 10.1145/321958.321975 , hdl : 10338.dmlcz/103883 , MR   0408313 .

Дальнейшее чтение

[ редактировать ]
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 97be159150ea0e074959de770fab4301__1723005360
URL1:https://arc.ask3.ru/arc/aa/97/01/97be159150ea0e074959de770fab4301.html
Заголовок, (Title) документа по адресу, URL1:
Hardness of approximation - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)