Questions tagged [pspace]
The pspace tag has no usage guidance.
57 questions
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-...
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. ...
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 ...
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 ...
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 ...
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:
...
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 ...
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 ...
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.
...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
1
vote
0
answers
224
views
anything hinting that EXPTIME $\subseteqq$ PSPACE?
Anything or evidence hinting that $$EXPTIME \subseteqq PSPACE$$?
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 ...
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 ...
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 ...
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-...
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 ...
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 ...
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{...
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 ...
-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?
-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 ...
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 ...
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 ...
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.
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, ...
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$?
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....
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 ...
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 ...
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,...
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 ...
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 ...
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 ...
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 $...
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 ...
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?
...
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 ...
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 ...
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. ...
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 ...
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 ...
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 ...
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)...
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-...
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 ...