Альтернативное понятие сложности, основанное на разрыве между грубой силой и лучшим алгоритмом?

Как правило, эффективные алгоритмы имеют полиномиальное время выполнения и экспоненциально большое пространство решений. Это означает, что проблема должна быть простой в двух смыслах: во-первых, проблема может быть решена за полиномиальное число шагов, и, во-вторых, пространство решений должно быть очень структурированным, поскольку время выполнения является только полилогарифмическим по числу возможных решений.

Однако иногда эти два понятия расходятся, и проблема проста только в первом смысле. Например, общая методика в алгоритмах аппроксимации и параметризованной сложности (примерно) состоит в том, чтобы доказать, что пространство решений может быть на самом деле ограничено гораздо меньшим размером, чем простое определение, а затем использовать грубую силу, чтобы найти лучший ответ в этом ограниченном пространстве. , Если мы можем априори ограничить себя, скажем, n ^ 3 возможными ответами, но нам все равно нужно проверить каждый из них, то в некотором смысле такие проблемы все еще «трудны», поскольку нет лучшего алгоритма, чем грубая сила.

И наоборот, если у нас есть проблема с двояко-экспоненциальным числом возможных ответов, но мы можем решить ее только за экспоненциальное время, то я хотел бы сказать, что такая проблема «проста» («структурированная» может быть лучше слово), так как время выполнения - только журнал размера пространства решения.

Кто-нибудь знает о каких-либо работах, в которых рассматривается что-то вроде твердости, основанной на разрыве между эффективным алгоритмом и грубой силой или твердостью относительно размера пространства решения?

Одна проблема с формализацией вопроса состоит в том, что фраза «пространство решения для проблемы А» не является четко определенной. Для определения пространства решений требуется алгоритм верификатора , который, учитывая экземпляр и возможное решение, проверяет, является ли решение правильным. Затем пространство решений экземпляра относительно верификатора представляет собой набор возможных решений, которые делают вывод верификатора «правильным».

Например, возьмем задачу SAT0: с учетом булевой формулы, удовлетворяется ли она присваиванием всех нулей? Эта проблема тривиально за полиномиальное время, но пространство ее решения может сильно различаться в зависимости от того, какой верификатор вы используете. Если ваш верификатор игнорирует возможное решение и просто проверяет, работают ли все нули на экземпляре, то «пространство решения» для любого экземпляра SAT0 на этом верификаторе тривиально: это все возможные решения. Если ваш верификатор проверяет, является ли решение-кандидат удовлетворительным назначением, то пространство решений экземпляра SAT0 может быть довольно сложным, возможно, таким же сложным, как пространство решений любого экземпляра SAT.

Тем не менее, проблема «избегания поиска методом грубой силы» может быть формализована следующим образом (как видно из статьи «Улучшение исчерпывающего поиска подразумевает суперполиномиальные нижние оценки»). Вам предоставляется алгоритм верификатора, который выполняется за время , в случаях размера n и возможных решениях k битов. Вопрос в том, * в произвольных случаях размера n , можем ли мы определить, существует ли правильное решение (с этим верификатором) с не более чем k битами, за намного меньшее, чем O ( 2 k t ( n , k ) ) время?$t(n,k)$$n$$k$$n$$k$$O(2^k t(n,k))$

$O(2^k t(n,k))$$2^n$

В статье показаны некоторые интересные последствия улучшения поиска методом перебора некоторых проблем. Даже улучшение поиска методом "грубой силы" "пространств решений полиномиального размера" будет иметь интересные последствия.

Как бы вы справились с типичными проблемами динамического программирования? Здесь часто случается так, что пространство оптимальных решений ограничено полиномиально, а пространство решений - нет. Таким образом, это кажется «легким» в вашем смысле, потому что время выполнения является логарифмическим в пространстве решений, но это «сложно» в вашем смысле, потому что оно работает «грубой силой» над всеми потенциально оптимальными решениями.

Перспектива, кажется, предполагает некоторые вещи, такие как конечность пространств решений.

Например, подумайте о проблеме генерации тесселяции Вороного из набора входных точек. Здесь существует пространство решений бесконечного размера, так как каждая точка на краях диаграммы представляет собой набор действительных чисел. Тем не менее решение может быть достигнуто в O (n log (n)) в количестве входных точек (для плоскости).

С этим связаны проблемы, допускающие алгоритмы с полиномиальной задержкой . Первое решение и каждое последующее решение может быть сгенерировано за полиномиальное время. Джонсон, Яннакакис и Папдимитриу обсуждают эту структуру в контексте других возможных пробелов (таких как общее полиномиальное время): « О создании всех максимальных независимых наборов» , «Обработка информации», 27 , 119–123, 1988.