Я ищу класс сложности, который относится к APX, так как BPP относится к P. Я уже задавал этот же вопрос здесь , но, возможно, TCS будет более плодотворным местом для ответов.
Причина этого вопроса заключается в том, что в практических задачах часто приходится находить приблизительные ответы (например, APX) с достаточно высокой достоверностью (например, BPP), что делает класс задач с алгоритмами ограниченной вероятностной аппроксимации потенциально полезной моделью того, что вычисляется в практика.
Возможным кандидатом такого класса были бы : задачи, допускающие приближенные решения с ограниченными вероятностными подпрограммами; однако я не уверен, что такой класс будет подходящим параметром для вероятностно вычислимых приближений класса.
Как BPP, так и APX были тщательно изучены. Это тот случай, когда или какой класс лучше всего подходит для решения вышеуказанных проблем?
Ответы:
Для любой заданной целевой функции пусть BotL (best-of-the-list) будет алгоритмом, который оценивает целевую функцию на множестве входов и возвращает входные данные из этого списка, которые имели максимальный выход (из числа этих входов), со связями сломано произвольно.
, целевую функцию которых можно вычислить за детерминированное полиномиальное время, BotL можно реализовать детерминистически за полиномиальное время.
, по меньшей мере так же хорошо, как и любой из входных данных, по меньшей мере, на котором BotL был оценен.
если какой-либо из входов в этом списке достаточно хорош, то вывод BotL будет достаточно хорошим.
Поэтому запуск BotL на выходах достаточно большого числа независимых исполнений базового алгоритма может увеличить вероятность успеха с 1 / poly до 1- (1 / (2 ^ poly)).
Как следствие предыдущего абзаца, точный
уровень достоверности по существу не влияет на результирующий класс.
(Эта ситуация очень похожа на RP .)
Я не смог ничего найти об этом в зоопарке сложности, хотя,
возможно, об этом говорили на семинаре, упомянутом в этой статье .
источник