Classe de complexité associée à une recherche exhaustive

Quelle est la classe de complexité associée aux algorithmes de recherche exhaustifs? (Si il y en a un)

Est-ce NP ou PSPACE?

Existe-t-il des modèles de calcul restreints capturant la classe d'algorithmes de recherche exhaustifs similaires aux modèles de programmation gourmande et dynamique?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models Anonyme
la source

Plus approprié à cs.stackexchange.

Yuval Filmus

Et E ou EXP?

Yuval Filmus

@YuvalFilmus vraiment? Cela me semble être une question intéressante et pas du tout anodine

Suresh Venkat

Les différentes classes de recherche locales commencent par un espace de problème où une solution est garantie d'exister, et le défi est de rechercher l'espace en temps sous-exponentiel. Cela pourrait être lié.

Suresh Venkat

C'est un peu vague mais j'aime la question. J'ai écrit un article à ce sujet il y a longtemps. Peut-être que cela aidera le questionneur anonyme: stanford.edu/~rrwill/bfsearch-rev.ps [AVERTISSEMENT: il est probable que je suis en désaccord avec presque toutes les opinions exprimées ici, il a été écrit il y a 10 ans]

Ryan Williams

Réponses:

C'est un peu vague, mais j'aime la question. J'ai écrit un article à ce sujet il y a longtemps. Peut-être que cela aidera le questionneur anonyme:

Recherche de force brute et calcul basé sur Oracle

$P^{NP}$ $3$ $PSPACE$

[ AVERTISSEMENT AVERTISSEMENT AVERTISSEMENT: il est probable que je sois en désaccord avec presque toutes les opinions exprimées dans ce document. Il a été écrit il y a une dizaine d'années, par une personne du même nom mais essentiellement différente. ]

Ryan Williams
la source

J'adore l'avertissement! :)

Tayfun Pay