Доступ к оракулу обеспечит значительное, сверхполиномиальное ускорение для всего в (при условии, что набор не пуст). Тем не менее, не совсем ясно, сколько выиграет от этого доступа к оракулу. Конечно, ускорение в не может быть суперполиномиальным, но оно может быть полиномиальным. Например, можем ли мы найти кратчайший путь быстрее с оракулом , чем без него? Как насчет более сложных задач, таких как минимизация субмодульных функций или линейное программирование? Получат ли они (или другие естественные проблемы в ) выгоду от оракула ?N P - P P P S A T P S A T
В более общем смысле, если мы можем выбрать любую проблему в и использовать для нее оракула, то какая из проблем в может привести к ускорению?
cc.complexity-theory
np
np-complete
Андрас Фараго
источник
источник
Ответы:
На самом деле, принятие недетерминированных машин Тьюринга во время является O ( т войти т ) -время сводится к SAT (построение с помощью рассеянного моделирования, см Arora-Варак), поэтому , как правило , любого времени недетерминирована машина заметно быстрее , чем детерминированный , мы увидим хоть какое-то ускорение с оракулом SAT.t O(tlogt)
Чтобы быть более конкретным, на ум приходит тестирование простоты, так как наилучший вариант алгоритма AKS, по-видимому, проверяет простоту битного числа во времени O ( n 6n . Но если мы пойдем "старой школы", Пратт дал недетерминированный ТМ, чтобы решить первичность во времени O ( n 3O(n6polylogn) . Принятие этой машины может быть уменьшено (детерминировано) в O ( n 3O(n3polylogn) время для экземпляра SAT.O(n3polylogn)
Проблема 3SUM может быть другим примером, поскольку кажется, что можно угадать решение и проверить его в субквадратичном времени, и тогда прием такой машины может быть уменьшен до SAT в субквадратичном времени.
источник
Этот вопрос становится более прямым при представлении и времени, необходимом, чтобы уменьшить одну проблему до другой ....
Главный ответ, который я имею в виду, - это оракул целочисленного / линейного программирования. Версия решения этой проблемы является NP-полной. Существует тривиальное «сокращение» от линейного программирования, потому что это особый случай. Но оракул для одного только линейного программирования (не говоря уже о ILP) ускоряет многие проблемы, которые сразу же решаются линейным программированием. Они могут быть сведены к нему за линейное время, переписав задачу в виде LP. Например, кратчайшие пути и другие проблемы потока, сопоставления.
Но я не думаю, что ILP - единственный способ в любом случае, вероятно, люди больше не задумывались, например, о сокращении кратчайшего пути до TSP и так далее.
источник
источник