Самый неплотный разрез: различия между версиями

Показатели сложности аппроксимации для задачи о самом неплотном разрезе довольно слабы. Недавно Чужой и Ханна [9] показали, что эта задача является APX-сложной, то есть существует константа <math>\epsilon > 0</math>, такая, что <math>(1 + \epsilon)</math>-аппроксимационный алгоритм для нее будет означать равенство P=NP. Предполагается, что взвешенная версия задачи NP-сложна для аппроксимации с коэффициентом, лучшим, чем <math>O((log \; log \; n)^c)</math> для некоторой постоянной ''c'', но известно, что это верно только в предположении версии так называемой гипотезы об уникальной игре [8, 12]. С другой стороны, известно, что релаксация полуопределенного программирования Ароры и др. имеет разрыв целостности <math>\Omega (log \; log \; n)</math> даже в невзвешенном случае [10]. Доказательство безусловной суперконстантной сложности для взвешенного или невзвешенного варианта задачи о самом неплотном разрезе, а также получение <math>o(\sqrt{log \; n})</math>-аппроксимаций для этих задач остаются нерешенными вопросами.