Komplexitätsklasse im Zusammenhang mit umfassender Suche

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?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models Anonym
quelle

Eher geeignet für cs.stackexchange.

Yuval Filmus

Wie wäre es mit E oder EXP?

Yuval Filmus

@YuvalFilmus wirklich? Dies scheint mir eine interessante Frage zu sein und überhaupt nicht trivial

Suresh Venkat

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

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:

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

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

[ 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

Liebe die Warnung! :)

Tayfun Pay