Класс APX
Класс APX (от англ. «approximable») в теории вычислительной сложности — это класс NP-трудных задач, для которых существуют аппроксимационные алгоритмы полиномиальной сложности с постоянным коэффициентом аппроксимации. В более простых терминах, задачи этого класса имеют эффективные алгоритмы, находящие решения, которые хуже оптимального не более чем на фиксированный процент. Например, существует алгоритм полиномиальной сложности для решения задачи об упаковке в контейнеры, который использует не более чем на 5 % больше контейнеров, чем наименьшее необходимое их число.
Аппроксимационный алгоритм называется алгоритмом c-аппроксимации с некоторой константой c, если можно доказать, что решение, полученное с помощью этого алгоритма, хуже оптимального не более чем в c раз[1].
Константа c называется коэффициентом аппроксимации. В зависимости от того, является ли проблема проблемой максимизации или минимизации, решение может быть в c раз больше или в c раз меньше оптимального.
К примеру, и задача о вершинном покрытии, и задача коммивояжёра с неравенством треугольника имеют простые алгоритмы, для которых c = 2[2]. С другой стороны, доказано, что задачу коммивояжёра с произвольными длинами рёбер (не обязательно удовлетворяющими неравенству треугольника) нельзя аппроксимировать с постоянным коэффициентом, поскольку задачу поиска гамильтонова пути нельзя решить за полиномиальное время (в случае, если P ≠ NP)[3].
Если существует алгоритм решения задачи за полиномиальное время для любого фиксированного коэффициента большего единицы (один алгоритм для любого коэффициента), говорят, что задача имеет полиномиальную по времени схему аппроксимации (PTAS). Если P ≠ NP, можно показать, что существуют задачи, входящие в класс APX, но не в PTAS, то есть задачи, которые можно аппроксимировать с некоторым коэффициентом, но не с любым коэффициентом.
Задача называется APX-трудной, если любая задача из класса APX имеет сведение к этой задаче, и APX-полной, если задача APX-трудна и сама принадлежит к классу APX[1]. Из неравенства P ≠ NP следует, что PTAS ≠ APX, P ≠ NP, а отсюда никакая APX-трудная задача не принадлежит PTAS.
Если задача APX-трудна, это обычно плохо, поскольку при P ≠ NP это означает отсутствие PTAS-алгоритма, который является наиболее полезным видом аппроксимационного алгоритма. Одна из наиболее простых APX-полных задач — это задача максимальной выполнимости булевых формул, вариант задачи выполнимости булевых формул. В этой задаче мы имеем булеву формулу в конъюнктивной нормальной форме, и хотим получить максимальное число подвыражений, которые будут выполняться при единственной подстановке значений true/false в переменные. Несмотря на то, что, скорее всего, задача не принадлежит PTAS, верное значение может быть получено с точностью 30 %, а некоторые упрощённые варианты задачи имеют PTAS[4][5][6].
Примеры[править | править код]
Примечания[править | править код]
- ↑ 1 2 Tjark Vredeveld. Combinatorial approximation algorithms : guaranteed versus experimental performance. — Technische Universiteit Eindhoven, 2002. — P. 4,12. — ISBN 90-386-0532-3.
- ↑ by Dorit S. Hochbaum. Approximation algorithms for NP-hard problems. — PWS Publishing Company, 1995. — P. 94-144. — ISBN 0-534-94968-1.
- ↑ Sanjeev Arora. The Approximability of NP-hard Problems. — Princeton University.
- ↑ MICHEL X. GOEMANS, DAVID P. WILLIAMSON. NEW 3/4-APPROXIMATION ALGORITHMS FOR THE MAXIMUM SATISFIABILITY PROBLEM // SIAM J. DISC. MATH.. — 1994. — Т. 7, вып. 4. — С. 656-666.
- ↑ MICHEL X. GOEMANS, DAVID P. WILLIAMSON. Improved Approximation Algorithms for Maximum Cut and Satisfiability Problems Using Semidefinite // Journal of the Association for Computins Machinery. — 1995. — Т. 42, вып. 6. — С. 1115-1145.
- ↑ Miguel F. Anjos. Semidefinite Optimization Approaches for Satisfability and Maximum-Satisfability Problems // Journal on Satisfiability, Boolean Modeling and Computation. — 2005. — Т. 1. — С. 1-47.
Ссылки[править | править код]
- C. Papadimitriou and M. Yannakakis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425-440, 1991.
- Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski and Gerhard Woeginger. Maximum Satisfiability Архивная копия от 13 апреля 2007 на Wayback Machine. A compendium of NP optimization problems Архивная копия от 5 апреля 2007 на Wayback Machine. Last updated March 20, 2000.
| Считаются лёгкими | |
|---|---|
| Предполагаются сложными | |
| Считаются сложными | |
 | Для улучшения этой статьи желательно:
|