# Tagged Questions

The tag has no usage guidance.

265 views

### For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?

It is well known that the following problem is PSPACE-complete: Given regular expression $\beta$, does $L(\beta) = \Sigma^*$? What about determining equivalence to other (fixed) regular ...
78 views

### Space requirements for solving True Quantified Boolean Formulas problem [closed]

I came across this section on the wikipedia page for the TQBF solving problem, and just can't wrap my head about the fact that the space requirement is linear. Moreover, it does not provide any ...
89 views

### Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem? ...
180 views

### How can one ACTUALLY minimize a regular expression? [closed]

Minimizing regular expressions (in terms of number of symbols) is PSPACE-complete (for example as discussed here: minimizing size of regular expression). But how do you actually do that (i.e., what ...
508 views

### What are consequences of the collapse of CH?

I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important ...
409 views

### Have these coloring games been solved?

In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. ...
280 views

### Is there a simple game with asymmetric complexity?

Consider full information two-player combinatorial games that end after a polynomial number of moves, and in an alternating way, the players picks from a finite number of allowed moves. The usual ...
168 views

### Is there a gadget that reduces generalized geography to undirected graphs?

The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming ...
760 views

### Is this variation of TQBF still PSPACE-complete?

Deciding if a quantified boolean formula such as $\forall x_1 \exists x_2 \forall x_3\cdots \exists x_n \varphi(x_1, x_2,\ldots , x_n),$ always evaluates to true is a classical PSPACE-complete ...
261 views

297 views

### Is there a reduction to “door and pressure plate” games that doesn't explode solution length?

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 ...
172 views

### Is the complexity of ARC KAYLES still open?

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 ...
125 views

### Savitch's use of measurability

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 ...
898 views

### Complexity of Portal 2

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