Класс сложности, связанный с исчерпывающим поиском

14

Какой класс сложности связан с исчерпывающими алгоритмами поиска? (если есть)

Это NP или PSPACE?

Существуют ли ограниченные модели вычислений, охватывающие класс алгоритмов исчерпывающего поиска, аналогичных моделям для жадного и динамического программирования?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models анонимное
источник
6
Больше подходит для cs.stackexchange.
Юваль Фильмус
2
Как насчет E или EXP?
Юваль Фильмус
5
@YuvalFilmus действительно? Это кажется мне интересным и совсем не тривиальным вопросом
Суреш Венкат
1
Различные локальные классы поиска начинаются с проблемного пространства, где гарантированно существует решение, и задача состоит в том, чтобы искать пространство в субэкспоненциальном времени. Это может быть связано.
Суреш Венкат
5
Это немного расплывчато, но мне нравится вопрос. Я написал статью об этом давно. Может быть, это поможет Анонимному спрашивающему: stanford.edu/~rrwill/bfsearch-rev.ps [ВНИМАНИЕ: Вероятно, я не согласен почти со всеми высказанными там мнениями, написанными 10 лет назад]
Райан Уильямс,

Ответы:

21

Это немного расплывчато, но мне нравится вопрос. Я написал статью об этом долгое время назад. Может быть, в этом поможет Анонимный вопросник:

Поиск методом грубой силы и вычисления на базе Oracle

пNп3пSпAСЕ

[ ПРЕДУПРЕЖДЕНИЕ ПРЕДУПРЕЖДЕНИЕ ПРЕДУПРЕЖДЕНИЕ. Вероятно, я не согласен почти со всеми мнениями, изложенными в этом документе. Он был написан около 10 лет назад кем-то с таким же именем, но по сути другим человеком. ]

Райан Уильямс
источник
2
Люблю предупреждение! :)
Tayfun Pay