Komplexitätsklasse im Zusammenhang mit umfassender Suche

14

Welche Komplexitätsklasse ist mit umfassenden Suchalgorithmen verbunden? (wenn es einen gibt)

Ist es NP oder PSPACE?

Gibt es eingeschränkte Berechnungsmodelle, die die Klasse der umfassenden Suchalgorithmen erfassen, ähnlich den Modellen für gieriges und dynamisches Programmieren?

Anonym
quelle
6
Eher geeignet für cs.stackexchange.
Yuval Filmus
2
Wie wäre es mit E oder EXP?
Yuval Filmus
5
@YuvalFilmus wirklich? Dies scheint mir eine interessante Frage zu sein und überhaupt nicht trivial
Suresh Venkat
1
Die verschiedenen lokalen Suchklassen beginnen mit einem Problemraum, in dem es garantiert eine Lösung gibt, und die Herausforderung besteht darin, den Raum in subexponentieller Zeit zu durchsuchen. Es könnte verwandt sein.
Suresh Venkat
5
Es ist ein bisschen vage, aber ich mag die Frage. Ich habe vor langer Zeit eine Zeitung darüber geschrieben. Vielleicht hilft das dem anonymen Fragesteller: stanford.edu/~rrwill/bfsearch-rev.ps [WARNUNG: Es ist wahrscheinlich, dass ich mit fast allen dort vertretenen Meinungen nicht einverstanden bin, sie wurden vor 10 Jahren geschrieben]
Ryan Williams

Antworten:

21

Es ist ein bisschen vage, aber ich mag die Frage. Ich habe vor langer Zeit eine Zeitung darüber geschrieben. Vielleicht hilft das dem anonymen Fragesteller:

Brute Force Search und Oracle-basierte Berechnung

PNP3PSPEINCE

[ WARNUNG WARNUNG WARNUNG: Es ist wahrscheinlich, dass ich mit fast allen Meinungen in diesem Artikel nicht einverstanden bin. Es wurde vor ungefähr 10 Jahren von jemandem mit dem gleichen Namen geschrieben, der aber im Wesentlichen eine andere Person ist. ]

Ryan Williams
quelle
2
Liebe die Warnung! :)
Tayfun Pay