Classe de complexidade associada à pesquisa exaustiva

14

Qual é a classe de complexidade associada a algoritmos de pesquisa exaustivos? (se houver)

É NP ou PSPACE?

Existem modelos restritos de computação que capturam a classe de algoritmos exaustivos de pesquisa semelhantes aos modelos para programação dinâmica e gananciosa?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models Anônimo
fonte
6
Mais apropriado para cs.stackexchange.
Yuval Filmus
2
E quanto a E ou EXP?
Yuval Filmus
5
@YuvalFilmus realmente? Esta parece ser uma pergunta interessante para mim e nada trivial
Suresh Venkat
1
As várias classes de pesquisa local começam com um espaço problemático em que é garantida a existência de uma solução, e o desafio é pesquisar o espaço em tempo subexponencial. Pode estar relacionado.
Suresh Venkat
5
É um pouco vago, mas eu gosto da pergunta. Eu escrevi um artigo sobre isso há muito tempo. Talvez isso ajude o interlocutor anônimo: stanford.edu/~rrwill/bfsearch-rev.ps [AVISO: É provável que eu discorde de quase todas as opiniões declaradas lá, que foram escritas há 10 anos]
Ryan Williams

Respostas:

21

É um pouco vago, mas eu gosto da pergunta. Eu escrevi um artigo sobre isso há muito tempo. Talvez isso ajude o interlocutor anônimo:

Pesquisa de força bruta e computação baseada em Oracle

PNP3PSPACE

[ AVISO AVISO AVISO: É provável que eu não concorde com quase todas as opiniões declaradas neste documento. Foi escrito há cerca de 10 anos, por alguém com o mesmo nome, mas que é essencialmente uma pessoa diferente. ]

Ryan Williams
fonte
2
Ame o aviso! :)
Tayfun Pay