Skip to main content

Questions tagged [pspace]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
4 votes
1 answer
174 views

References for $\mathsf{PSPACE} \neq \mathsf{E}$ and $\mathsf{P} \neq \mathsf{NTIME}(n^k)$

In a recent blog post, Lance Fortnow dropped as a little exercise the task of proving $\mathsf{PSPACE} \neq \mathsf{E}$, using the fact that $\mathsf{EXP}$ is the closure of $\mathsf{E}$ under poly-...
Noel Arteche's user avatar
  • 1,049
4 votes
1 answer
120 views

Solving #SAT through TQBF

I'm not extremely proficient with counting complexity classes, but since #SAT is #P-complete, its decision version, let's call it #SAT(D) (is the number of solutions less than some $k$), is in PSPACE. ...
Nicola Gigante's user avatar
0 votes
0 answers
22 views

Natural reduction from partially observable Markov decision process planning to reconfiguration

Suppose I want to prove the PSPACE-completeness of reconfiguration by reducing partially observable Markov decision process (POMDP) planning to it. Is there a known natural / succinct reduction from ...
delete000's user avatar
  • 848
4 votes
1 answer
174 views

Does Rush-Hour (or Klotski) admit a search-to-decision reduction?

Consider puzzles like Rush-Hour or Klotski. When suitably generalized, such puzzles are known to be PSPACE-complete, but surely there is an interesting subclass of instances intesecting NP (and not ...
Mark S's user avatar
  • 1,145
4 votes
1 answer
165 views

Intersection Non-Emptiness for Two-Way Finite Automata

We know that checking the emptiness of intersection of an unbounded number of deterministic finite automata is PSpace-complete, and that just the emptiness problem for a nondeterministic two-way ...
A. G.'s user avatar
  • 43
1 vote
0 answers
83 views

Separating disjoint PSPACE-hard sets by NP-separators (and some variants)

I am trying to find some references or arguments for results of the form, where $X,Y$ vary over complexity classes, typically with $X\subseteq Y$, and $A,B$ are disjoint languages that are $Y$-hard: ...
Anupam Das's user avatar
1 vote
0 answers
81 views

Why is the model-checking problem for MSO $\textsf{PSPACE}$-complete?

I am currently reading "Parameterized Complexity Theory" by J. Flum and M. Grohe. In Chapter 10.3 they state in the first paragraph: Let us remind the reader that the model-checking problem ...
user11718766's user avatar
3 votes
0 answers
95 views

Complexity of chess with 50-move rule

It is known that evaluating who wins in $n \times n$ chess positions is EXP-complete (and thus unconditionally not in P), and this effect is due to the game having rich possibilities for exponentially ...
Alexey Slizkov's user avatar
1 vote
0 answers
91 views

What complexity class is characterized by having PSPACE verifiers?

Inspired by the 2 definitions (theorems) I am aware of, that are as follows. A language L belongs to QMA if there exists a BQP verifier V. A language L belongs to NP if there exists a P verifier V. ...
Ilk's user avatar
  • 930
0 votes
0 answers
147 views

Could we build PSPACE-based cryptography - more secure post-quantum?

It seems not safe to exclude possibility of e.g. some next generation quantum computers being able to attack NP problems (e.g. 2WQC) - so maybe it is worth to start thinking of shifting the ...
Jarek Duda's user avatar
4 votes
1 answer
327 views

is SUBEXP contained within PSPACE?, NP?

Let SUBEXP is the complexity class of all problems solvable in sub-exponential time in the length of the input. What are the known properties of this class? Is it known to be contained in PSPACE, if ...
Colonizor48's user avatar
3 votes
1 answer
249 views

Which 1-player games are EXPTIME-complete? Also, are there any known games that are EXPSPACE-complete?

I noticed a lot of 1-player games have been shown to be NP-Hard, like Pac-Man, The World's Hardest Game, Tetris, etc. For PSPACE-Complete, I noticed that Wikipedia listed these 1-player games: It is ...
edit's user avatar
  • 33
7 votes
1 answer
425 views

Is $PSPACE$ believed to be different than $PP$?

From Googling, I couldn't find any discussion about whether $PP=PSPACE$ is more or less likely than $PP\subsetneq PSPACE$. Is it currently believed that $PP\neq PSPACE$? What would be the ...
M A's user avatar
  • 215
5 votes
1 answer
248 views

How hard is Hex from a symmetric position?

It is known that determining who wins Hex from an arbitrary position is PSPACE-vollständig but of course a strategy stealing argument guarantees that the first player wins on the empty board or, more ...
domotorp's user avatar
  • 14.2k
5 votes
0 answers
95 views

Complexity of inclusion of transfinite expressions

Transfinite expressions on an alphabet $\Sigma$ are generated by the grammar : $$e,f:= a\in\Sigma\mid e\cdot f\mid e+f\mid e^*\mid e^\omega.$$ They describe languages of transfinite words, i.e. words ...
Denis's user avatar
  • 9,018
1 vote
0 answers
224 views

anything hinting that EXPTIME $\subseteqq$ PSPACE?

Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$?
XL _At_Here_There's user avatar
3 votes
0 answers
247 views

PSPACE-complete under NP reduction

Is there some example of a PSPACE problem that we can show PSPACE-hard under NP reduction, but we do not know a proof of PSPACE-hardness under P reduction ? To be more precise, the NP reduction I am ...
Denis's user avatar
  • 9,018
1 vote
1 answer
143 views

Quantum complexity of TQBF with an untrusted oracle

This is a follow up to Quantum complexity of TQBF, trying to model the situation where we have good heuristics. Let $L$ be the language of true, fully alternating totally quantified boolean formulas ...
Geoffrey Irving's user avatar
7 votes
1 answer
221 views

Quantum complexity of TQBF

There is no classical algorithm for $n$-bit TQBF with better than $O(2^n)$ complexity. Is that also the best known bound for quantum algorithms / circuits? Edit: As pointed out by Huck Bennett, in ...
Geoffrey Irving's user avatar
4 votes
0 answers
316 views

Deciding whether $2^k+m$ is prime

I thought something fancy can be done with number-theory or memoization, but neither worked for me. Being limited in knowledge I decided to ask experts. Does there exist a deterministic polynomial-...
The T's user avatar
  • 159
4 votes
0 answers
180 views

LogSpace reductions vs. PTime reductons for defining PSpace-completeness

Continuing https://cs.stackexchange.com/questions/90527/is-every-pspace-complete-problem-complete-with-respect-to-logspace-reductions : earlier, PSPACE-completeness was defined via logspace reductions ...
MdAyq's user avatar
  • 91
8 votes
0 answers
237 views

Conditional separations of $\exists\mathbb{R}$ from $\mathbf{PSPACE}$

As pointed out explicitly by Emil Jeřábek here: Even with Turing reductions, $\mathbf{PSPACE}=\mathbf{P}^{\exists\mathbb{R}}$ would still be a breakthrough (and completely unexpected) result. So ...
Thomas Klimpel's user avatar
9 votes
1 answer
342 views

Evidence for $\mathsf{P} \neq \mathsf{PP}$ if the polynomial hierarchy collapses?

We think that $\mathsf{PH}$ does not collapse, and that $\mathsf{PP}$ is not in $\mathsf{P}$. Suppose on the contrary that $\mathsf{PH}$ does collapse, say even $\mathsf{P}= \mathsf{NP}$. $\mathsf{...
Turbo's user avatar
  • 13.3k
8 votes
1 answer
441 views

Does $\exists\mathbb{R}=\mathbf{PSPACE}$?

The complexity class $\exists \mathbb{R}$ (the existential theory of the reals, i.e. problems that can be reduced to deciding if a collection of polynomial inequalities has a solution) is known to be ...
wrvb's user avatar
  • 183
-2 votes
1 answer
288 views

Why $PSPACE!=Dtime(2^n)$? [closed]

Why $PSPACE != Dtime(2^n)$? I can not see how padding argument can help here, how can it be proven?
student's user avatar
-2 votes
1 answer
655 views

Why is it a mystery if PSPACE ?= EXPTIME?

It seems obvious to me that $PSPACE \neq EXPTIME$. I, however, do not believe that my seemingly obvious logic would not be picked up by more intelligent people if it was so simple, so I'm assuming ...
user2894959's user avatar
3 votes
0 answers
834 views

Implications of resolving $BPP$ vs $PSPACE$

The relationship between the complexity classes $BPP$, $P$, and $NEXP$ is currently undetermined. We know that $P \neq EXP$ by the time hierarchy theorem, but we don't know if $BPP = P$ (as many ...
Mike Battaglia's user avatar
8 votes
0 answers
167 views

Practical interactive proof schemes for NP-hard problems

Model-checking (in the sense of reachability in a succinct graph) is PSPACE-complete. SAT is NP-complete. Both problems are considered intractable, yet there exist tools capable of solving them on ...
David Monniaux's user avatar
2 votes
1 answer
379 views

How to prove $P^{Halt} = PSPACE^{Halt}$ [closed]

Halt means the halting set. $PSPACE^{Halt}$ is the class of problems that can be solved with polynomial memory (possibly exponential time), given a halting oracle.
Michael's user avatar
  • 57
17 votes
0 answers
397 views

Intermediate problems between PSPACE and EXPTIME

Intermediate problems between P and NP are quite famous, and are sometimes considered as complexity classes by themselves. Do you know of any problem that is known to be PSPACE-hard and in EXPTIME, ...
Denis's user avatar
  • 9,018
4 votes
1 answer
1k views

Does P = NP imply NP being a strict subset of PSPACE? [closed]

Does $\textbf{P} = \textbf {NP}$ imply that $\textbf{NP} \subsetneq \textbf{PSPACE}$? Or, for a slightly stronger result, does it imply that $\textbf{NL} = \textbf P$?
Columbo's user avatar
  • 143
9 votes
1 answer
539 views

Does there exist an oracle $A$ such that $(P^{\#P})^{A} \neq PSPACE^{A}$?

Background We know that $P^{\#P} \subseteq PSPACE$. In addition, we known from Toda's theorem that $PH \subseteq P^{\#P}$. For more background on $\#P$, see here: https://en.wikipedia....
Michael Wehar's user avatar
18 votes
1 answer
887 views

What is the minimum complexity oracle that separates PSPACE from the polynomial hierarchy?

Background It is known that there exists an oracle $A$ such that, $PSPACE^A \neq PH^A$. It is even known that the separation holds relative to a random oracle. Informally, one may interpret ...
Michael Wehar's user avatar
4 votes
0 answers
159 views

More powerful generator than Nisan-Wigderson one

Nisan-Wigderson generator can be computed in $\log^{O(1)} n$ space and fools all constant-depth circuits of size poly($n$). I mean Theorem 5 here. I want another generator, that can be computed in ...
Alexey Milovanov's user avatar
10 votes
0 answers
160 views

Checking a long product of matrices

Given a set of n-by-n integer matrices $\{A_1, \dots, A_m\}$, for a word $w=w_1 w_2\cdots w_l$ over $\{1, \dots, m\}$, we define $A_w:=A_{w_1}\cdots A_{w_l}$. The question is to decide, given $\{A_1,...
maomao's user avatar
  • 1,365
9 votes
1 answer
266 views

Consequences of a distillation algorithm for PSPACE

The following notion of a distillation algorithm comes from "On Problems Without Polynomial Kernels". Let a language $L$ be given. A distillation algorithm for $L$ takes a given list of input ...
Michael Wehar's user avatar
5 votes
0 answers
204 views

Easy interactive proofs for easy problems?

Motivation Consider some $L \subseteq \{0,1\}^*$. Suppose Alice gives Bob a machine or oracle $M$ that purportedly decides $L$. If Bob has only polynomial time in their disposal, then they cannot ...
Vanessa's user avatar
  • 2,181
1 vote
0 answers
52 views

Circuit games in extensive form with imperfect information

Consider $l,m,n,N \in \mathbb{N}$ and circuits $C: \{0,1\}^{l+m} \rightarrow \{0,1\}^l$, $D: \{0,1\}^{l+n} \rightarrow \{0,1\}^l$. Consider the following zero-sum two-layer extensive-form game with ...
Vanessa's user avatar
  • 2,181
23 votes
1 answer
606 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 expressions $...
mikero's user avatar
  • 2,809
2 votes
1 answer
382 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 ...
Nicolas Mattia's user avatar
2 votes
0 answers
135 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? ...
Turbo's user avatar
  • 13.3k
5 votes
1 answer
3k 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 ...
lukas.coenig's user avatar
27 votes
1 answer
947 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 ...
neophyte's user avatar
  • 541
12 votes
2 answers
928 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. ...
user32149's user avatar
  • 313
11 votes
3 answers
364 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 ...
domotorp's user avatar
  • 14.2k
7 votes
1 answer
404 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 ...
domotorp's user avatar
  • 14.2k
32 votes
3 answers
2k 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 ...
JWM's user avatar
  • 752
8 votes
0 answers
354 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 $\Omega(n^k)...
Jeremy Kun's user avatar
  • 1,328
15 votes
1 answer
649 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 PSPACE-...
R B's user avatar
  • 9,508
2 votes
0 answers
76 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 ...
Shaull's user avatar
  • 5,636