Pytania otagowane jako pspace

3
Czy ta odmiana TQBF jest wciąż kompletna z PSPACE?
Decydowanie, czy skwantyfikowana formuła boolowska, taka jak ∀ x1∃ x2)∀ x3)⋯ ∃ xnφ ( x1, x2), … , Xn) ,∀x1∃x2∀x3⋯∃xnφ(x1,x2,…,xn),\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n), zawsze ocenia na prawdę, to klasyczny problem z PSPACE. Można to postrzegać jako grę między dwoma graczami, z naprzemiennymi …
1
Jaka jest wyrocznia o minimalnej złożoności, która oddziela PSPACE od hierarchii wielomianowej?
tło Wiadomo, że istnieje oracle tak, że .P S P A C E A ≠ P H AAAAPSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A Wiadomo nawet, że separacja dotyczy przypadkowej wyroczni. Nieformalnie można to interpretować w ten sposób, że istnieje wiele wyroczni, dla których i są osobne.P HPSPACEPSPACEPSPACEPHPHPH Pytanie Jak skomplikowane są te wyrocznie, …
1
Czy kompletność PSPACE oznacza twardość aproksymacyjną?
W komentarzu w innym poście z cstheorySE wspomniano, że kompletność PSPACE implikuje twardość APX. Czy ktoś może wyjaśnić / udostępnić referencję? Czy to jest „ciasne”? (tj. czy istnieją problemy kompletne z PSPACE, których problem optymalizacji dopuszcza stałe przybliżanie współczynnika w czasie wielopunktowym? Co z kompletnością dla pewnego poziomu PH? Czy …
1
Czy te gry kolorowanki zostały rozwiązane?
W artykule „O złożoności niektórych gier koloryzujących” Bodlaender podaje kilka otwartych pytań na temat złożoności decydowania, czy gracz 1 lub 2 ma strategię wygrywającą w niektórych grach kolorystycznych. Czy ktoś wie, czy zostały rozwiązane? 1) W jednej grze dwóch graczy wybiera kolejno jeden wierzchołek na wykresie i odpowiednio koloruje go …
3
Czy istnieje ograniczenie do gier typu „drzwi i płyta dociskowa”, które nie eksplodują długości rozwiązania?
Ten dokument stanowi dowód, że w grze z drzwiami i płytkami dociskowymi trudno jest ustalić, czy awatar (gracza) może dotrzeć do danego miejsca. Dowodzi tego redukcja z TQBF , a długość powstałych rozwiązań zależy wykładniczo od liczby uniwersalnych kwantyfikatorów we wzorze. Czy istnieje redukcja z maszyny NPSPACE do takiej gry, …
3
Czy istnieje prosta gra o asymetrycznej złożoności?
Rozważ pełną informację dla dwóch graczy w kombinatorycznych grach, które kończą się po wielomianowej liczbie ruchów, i naprzemiennie gracze wybierają z ograniczonej liczby dozwolonych ruchów. Zwykle pytanie brzmi, jak trudno jest powiedzieć zwycięzcy z danej pozycji. Innym byłoby to, jak trudno wybrać zwycięski ruch ze zwycięskiej pozycji. (Tutaj nazywam ruch …
1
Jaka jest złożoność obliczania liczby rozwiązań problemu P-Space Complete? Co powiesz na klasy o wyższej złożoności?
Chyba nazywa się to # P-Space, ale znalazłem tylko jeden artykuł niejasno o tym wspominając. Co powiesz na liczącą się wersję problemów EXP-TIME-Complete, NEXP-Complete oraz EXP-SPACE-Complete? Czy są jakieś wcześniejsze prace, które można przytoczyć w odniesieniu do tego lub dowolnego rodzaju włączenia lub wyłączenia, takiego jak Toda's Torem?
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.