Клас 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-повних задач — це задача найбільшої виконуваності булевих формул[en], варіант задачі здійсненності булевих формул. У цій задачі ми маємо булеву формулу в кон'юнктивній нормальній формі, і хочемо отримати найбільшу кількість підвиразів, які будуть виконуватися за єдиної підстановки значень true/false у змінні. Попри те, що, найпевніше, задача не належить до PTAS, правильне значення можна отримати з точністю 30 %, а деякі спрощені варіанти задачі мають PTAS[4][5][6].

Приклади

Примітки

  1. ↑ а б Tjark Vredeveld. Combinatorial approximation algorithms : guaranteed versus experimental performance. — Technische Universiteit Eindhoven, 2002. — P. 4,12. — ISBN 90-386-0532-3.
  2. ↑ by Dorit S. Hochbaum. Approximation algorithms for NP-hard problems. — PWS Publishing Company, 1995. — P. 94-144. — ISBN 0-534-94968-1.
  3. ↑ Sanjeev Arora. The Approximability of NP-hard Problems. — Princeton University.
  4. ↑ 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.
  5. ↑ 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.
  6. ↑ 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 [Архівовано 2007-04-13 у Wayback Machine.]