Pytania oznaczone «pspace»

12
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...

11
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...