Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Category:

Неудобный вопрос.

https://en.wikipedia.org/wiki/NP_(complexity)

Если у нас обычная машина Тьюринга и мы можем искать только одно решение (ну, d=2O(1) решений), мы можем решить NP-полную проблему за время 2O(N). Если у нас не детерминированная машина Тьюринга и мы можем одновременно искать d=2O(N) решений, мы можем решить NP-полную проблему за время 2O(log(poly(N))).

Экспоненциальное количество поисков приводит к полиномиальному времени. Один поиск приводит к экспоненциальному времени.

Собственно, неудобный вопрос: а что находится посередине? Где d=O(poly(N)), больше, чем константа и меньше, чем экспонента.

Как известно, CDCL (поиск решения NP-полной задачи с запоминанием ограничений, вызванных конфликтами) экспоненциально быстрее обычного DPLL. Всего 4 процесса CDCL с немного разными параметрами, пущенные параллельно и имеющие возможность обмениваться найденными ограничениями, быстрее, чем один процесс CDCL.

А если таких процессов запустить O(poly(N))? Каково будет время решения?
Tags: sat. cdcl
Subscribe

  • Смею заметить.

    Увеличение цен на газ приводит к обнищанию Европы. Нищих проще поднять на войну. На этом у меня всё.

  • Знаки

    Чтобы система поддержки цепочки блоков была по-настоящему справедливой, необходимо, чтобы любой бит в блоке был неотличим от любого другого бита. В…

  • Случайный поиск.

    Вот пример решателя SAT, основанного на случайном поиске вокруг текущего присваивания: http://fmv.jku.at/yalsat/ Основной алгоритм у него таков:…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 2 comments