Минимальная бисекция: различия между версиями

Неизвестно, является ли эта задача APX-полной, однако некоторые результаты позволяют предположить такую возможность. Буй и Джонс [4] показали, что для любого фиксированного значения <math>\epsilon > 0 \;</math> задача аппроксимации минимальной бисекции с дополнительным членом <math>n^{2 - \epsilon} \;</math> будет NP-полной. Фейге [7] показал, что если опровержение для задачи выполнимости булевых формул в k-конъюнктивной нормальной форме в случае k=3 является сложным в среднем на реальном распределении входных данных, то для любого фиксированного значения <math>\varepsilon > 0 \;</math> не существует алгоритма <math>(4/3 - \varepsilon \;)</math>-аппроксимации задачи о минимальной бисекции. Хот [12] доказал, что для нахождения минимальной бисекции неприменима схема аппроксимации с полиномиальным временем выполнения (PTAS), за исключением случая, если класс NP включает рандомизированные алгоритмы с субэкспоненциальным временем выполнения.