Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

327 questions
Filter by
Sorted by
Tagged with
198 views

PSpace-completeness under PSpace reductions

A language $L$ is PSpace-complete, if it meets two conditions: It is in PSpace. Every other PSpace-complete language reduces to it in polynomial time. Question: suppose we change the second ...
59 views

Limited oracle TM

Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/...
210 views

Natural logspace complete problems

After Omer Reingold's famous proof (from 2005?) that SL = L, the distinction between natural L complete problems and natural SL complete problems has been mostly dropped, so that it became difficult ...
376 views

How to prove that $n\log n$ is space constructible?

I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that ...
2k views

Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
128 views

Proving SAT is in L

How to prove that SAT is in L if and only if NP=L? I know that reducing SAT in cook-levin theorem is computable in deterministic linear space . How to do it in log space? Any reference will also help.
26 views

348 views

69 views

How large would a database containing perfect knowledge of chess be?

Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-...
Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$
If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...