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

  • 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