We already know that determining whether a CFG grammar generates a string is P-complete, and whether a CSG grammar generates a string is PSPACE-complete. We also know that some CSG languages are not ...
This paper gives a proof that in a game with doors and pressure plates, it is PSPACE-hard to determine whether or not the (player's) avatar can reach a given location. This is proven by a reduction ...
In the problem NODE KAYLES two opposing players take turns playing on an undirected graph. In each turn, a player selects a vertex $u$ and removes $u$ and all its neighbors from the graph. The first ...
In Savitch's 1969 paper, "Relationships Between Nondeterministic and Deterministic Tape Complexities", he states that "all common storage functions L(n) >= lg n are measurable. In particular, any ...
I am studying the complexity of Portal 2 and I would like to know if the problem has been studied before. In particular, I would be interested any reference discussing the complexity of Portal 2 and ...
wikipedia entry says without reference that "There are even some context-sensitive grammars whose fixed grammar recognition problem is PSPACE-complete." This is stronger than saying that CSG is ...
What is the complexity of counting the number of solutions of a P-Space Complete problem? How about higher complexity classes?
I guess it would be called #P-Space but I have found only one article vaguely mentioning it. How about the counting version of EXP-TIME-Complete, NEXP-Complete as well as EXP-SPACE-Complete problems? ...