Klasa złożoności związana z wyczerpującym wyszukiwaniem

Jaka klasa złożoności jest powiązana z wyczerpującymi algorytmami wyszukiwania? (jeśli jest)

Czy to jest NP czy PSPACE?

Czy istnieją ograniczone modele obliczeń przechwytujące klasę wyczerpujących algorytmów wyszukiwania podobnych do modeli dla chciwego i dynamicznego programowania?

cc.complexity-theory ds.algorithms reference-request big-picture machine-models Anonimowy
źródło

Bardziej odpowiednie dla cs.stackexchange.

Yuval Filmus,

Co powiesz na E lub EXP?

Yuval Filmus,

@YuvalFilmus naprawdę? Wydaje mi się to interesującym pytaniem i wcale nie trywialnym

Suresh Venkat

Różne lokalne klasy wyszukiwania zaczynają się od przestrzeni problemu, w której istnieje rozwiązanie, a wyzwaniem jest przeszukanie przestrzeni w czasie podwykonawczym. To może być powiązane.

Suresh Venkat

To trochę niejasne, ale podoba mi się pytanie. Dawno temu napisałem o tym artykuł. Może to pomoże anonimowemu pytającemu: stanford.edu/~rrwill/bfsearch-rev.ps [OSTRZEŻENIE: Prawdopodobnie nie zgadzam się z prawie wszystkimi opiniami tam zawartymi, napisano 10 lat temu]

Ryan Williams

Odpowiedzi:

To trochę niejasne, ale podoba mi się pytanie. Napisałem o tym artykuł już dawno temu. Może to pomoże anonimowemu pytającemu:

Wyszukiwarka Brute Force i obliczenia oparte na Oracle

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

[ OSTRZEŻENIE OSTRZEŻENIE OSTRZEŻENIE: Prawdopodobnie nie zgadzam się z prawie wszystkimi opiniami zawartymi w tym dokumencie. Został napisany około 10 lat temu przez osobę o tym samym nazwisku, ale która zasadniczo jest inną osobą. ]

Ryan Williams
źródło

Uwielbiam ostrzeżenie! :)

Tayfun Zapłać