Tagged Questions

The tag has no wiki summary.

learn more… | top users | synonyms

8
votes
1answer
94 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 ...
-1
votes
0answers
63 views

Is this construction of large monotone boolean formulas in Exp or PSpace?

For every boolean formula $P$ on $N$ variables there exists a monotone formula $Q$ on $N$ variables that decides all QBFs of $P$ (QBFs are decided by evaluating assignments to $Q$). The formula $Q$ ...
22
votes
2answers
472 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 ...
8
votes
0answers
204 views

Linear space language that requires exponential time without ETH

The $\mathsf{P} \neq \mathsf{PSpace}$ conjecture means that There is a language $L \in \mathsf{DSpace}(O(n^t))$ for some $t>0$ such that for all positive integers $k$, $L$ requires ...
14
votes
1answer
334 views

Does PSPACE-completeness imply approximation hardness?

It is mentioned in a comment in another cstheorySE post that PSPACE-completeness imply APX-hardness. Can anyone please explain/share a reference for it? Is this "tight"? (i.e., are there ...
1
vote
0answers
58 views

Different hardness proofs w.r.t different classes

Consider a language $L$ which is hard for some class $C$ (e.g. PSPACE-hard). Trivially, $L$ is also $D$-hard for every class $D\subseteq C$ under the same type of reduction (e.g. NP-hard). Is there a ...
6
votes
1answer
145 views

Coding theory and complete problems

Coding theory is an useful topic in theoretical computer science. There are known examples of problems coming from coding theory which turn out to be NP complete. My questions are the following: ...
11
votes
3answers
262 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 ...
7
votes
0answers
115 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 ...
8
votes
1answer
122 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 ...
2
votes
3answers
802 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 ...
1
vote
2answers
317 views

are there fixed context sensitive grammars which are PSPACE complete?

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 ...
9
votes
1answer
340 views

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