Asymptotic analyses of the space needed to run algorithms.

learn more… | top users | synonyms

2
votes
2answers
83 views

Has there been any more progress on P vs. PSPACE compared to P vs. NP?

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown ...
-1
votes
0answers
17 views

pebbling is DSPACE($O(n^2)$) [closed]

Given a DAG $G$ and a vertex $v$ , consider the following game: We can place a pebble on a vertex $u$ if all its predecessors have pebbles on them. We can remove a pebble from a vertex any time. The ...
1
vote
0answers
42 views

Clique and PSPACE [closed]

I was wondering how I could go about creating an algorithm that gets all the cliques in a graph in PSPACE So far, based on some of the readings I've done, I am considering to use bit-strings (that ...
2
votes
1answer
29 views

What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity?

Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$. What is the best time and space complexity of calculating $n!$? P.S. I do not have any idea about this topic. I ...
2
votes
1answer
34 views

Polynomial space complexity with exponential size witnesses

Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has: Input tape: Read only, move in both directions. Witness tape: Read only, move only in one ...
2
votes
0answers
11 views

Generalized Geography with repetitions [duplicate]

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move ...
1
vote
1answer
58 views

Generalized Geography with repetitions

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to ...
2
votes
1answer
85 views

Log-Space Reduction $CO-2Col \le_L USTCON$

I want to show that $CO-2Col \le_L USTCON$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. [Input]: An undirected graph $G=(V,E)$, ...
2
votes
1answer
85 views

The crux of Savitch's Theorem

In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going ...
1
vote
0answers
57 views

How to Study Space Complexity

I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially ...
2
votes
1answer
46 views

Language with $\log\log n$ space complexity?

We know that every non-regular language can be recognized with $ \Omega (\log\log n) $ space complexity. I'm looking for an example of a language which is $ \Theta (\log\log n) $ space complexity ...
1
vote
1answer
24 views

ALL_{REGEX} in PSPACE algorithm

$ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$. In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ ...
4
votes
1answer
108 views

Relation of Space and Time in Complexity?

I'm looking for some clarification on some concepts/facts I came across while studying for a class. I was reading the following wikipedia article. The below specific section and statement intrigued ...
1
vote
1answer
31 views

Logspace Transducer

I know that a logspace transducer is a deterministic Turing machine that enables us to use log-space complexity. I do not understand though why that is correct. Whatever algorithms can be implemented ...
0
votes
0answers
44 views

Need an upper bound for node degree

I have a social network in the form of an undirected graph $G = (V,E)$ with distinct non-negative integer keys. For each node $u \in V$, let the set $\Gamma(u) = \{ v \in V : (u,v) \in E \}$ be the ...
6
votes
2answers
152 views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with ...
5
votes
2answers
94 views

Is DSPACE properly contained in NSPACE?

It may be a dumb question, but is $\mathsf{DSPACE}(f(n)) \subset \mathsf{NSPACE}(f(n))$ or is $\mathsf{DSPACE}(f(n)) \subseteq \mathsf{NSPACE}(f(n))$? In other words, is the containment relation ...
1
vote
1answer
37 views

If a problem is PSPACE-complete what do we know about NL-completeness

I have a problem $A$ which was shown to be PSPACE-complete by reduction from planning. However, $A$ can also be transformed into reachability problem which is NL-complete. I know that ...
3
votes
1answer
86 views

Relation between space and time complexity for machines with write once read many (WORM) memory

While thinking about different calculi for predicate logic (like natural deduction and sequent calculus), I noticed that these calculi are (often) presented in a form suitable for "human computers". A ...
2
votes
1answer
112 views

Prove that $TQBF \notin SPACE(n^{\frac{1}{3}})$

I would like some hints on how to approach this problem, I know for instance that $TQBF$ is $PSPACE$-$Complete$, so it can solved in poly space and any other $PSPACE$-$Complete$ problems can be log ...
1
vote
1answer
75 views

Proving that the language SPACE TMSAT is PSPACE-complete? [closed]

I'm trying to prove that the language SPACE TMSAT (where SPACE TMSAT = {⟨$M$, $w$, $1^n$⟩ : DTM $M$ accepts $w$ in space $n$}) is PSPACE-complete. My solution is as follows: SPACE TMSAT $= ...
2
votes
1answer
80 views

Known bounds on space complexity of multiplication decision problem

Given three numbers $m$, $n$ and $p$ in interleaved binary encoding1, it's obviously possible to check in $O(1)$ space whether $m+n=p$. It's less obvious2 that it isn't possible to check in $O(1)$ ...
1
vote
2answers
415 views

Memory complexity?

I am unclear about finding the memory complexity of an algorithm. Some places refer memory complexity as what container would be carrying for instance: ...
5
votes
1answer
101 views

NTIME(f) subset of DSPACE(f)

As the question states, how do we prove that $\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n))$? Can anyone point me to a proof or outline it here? Thanks!
2
votes
1answer
128 views

Set combination data structure (And storage complexity)

I have already posted this question on Stackoverflow, but I'm starting to think that this is the right place. I have a problem where I am required to associate unique combinations from a set (unique ...
5
votes
1answer
167 views

Is the memory-runtime tradeoff an equivalent of Heisenberg's uncertainty principle?

When I work on an algorithm to solve a computing problem, I often experience that speed can be increased by using more memory, and memory usage can be decreased at the price of increased running time, ...
4
votes
1answer
144 views

Checking whether a directed graph on n vertices contains exactly 10*sqrt(n) strongly connected components is in non-deterministic logspace

I am studying now for a test in my complexity course. When I solved previous exams I saw the following question : Prove that the language $L$ of all directed graphs on $n$ vertices that contain ...
4
votes
0answers
53 views

'Stones' game complexity

I'm trying to find complexity class of finding winning strategy for first player in following game: Intance of 'Stones' game is: finite set $X$ relation $R \subseteq X^3$ set $Y \subseteq X$ and ...
4
votes
2answers
62 views

Proving language in Space Complexity

I'd like to know if I have the right intuition and my answer is headed the correct way. I am given a function $ f = \{0, 1\}^* \rightarrow \{0, 1\}^* $ that is computable in space $O(\log n)$ assume ...
3
votes
1answer
194 views

Proving that Turing Machine M runs in time $O(2^{dn})$

I'm trying to solve this question in order to review for my exam, and this one has got me a bit stumped. From the looks of it, it seems like a fairly straight-forward question, but I can't figure out ...
1
vote
1answer
44 views

Showing transitivity of PSPACE?

For the following question: If B is an element of PSPACE and A is an element of PSPACE-Complete, and A polynomial reduces to B, then B is an element of PSPACE-Complete. I am trying to prove this, ...
5
votes
1answer
175 views

What is a compact way to represent a partition of a set?

There exist efficient data structures for representing set partitions. These data structures have good time complexities for operations like Union and Find, but they are not particularly ...
5
votes
4answers
283 views

Space complexity for finding the minimum number outside the list of numbers

We are given an (unsorted) list $L=(a_1,\dots,a_n)$ of numbers of size $n$, where $a_i\in \{ 1,\dots,B\}$. We want to find the minimum number $x$ from $\{ 1,\dots,B\} \backslash L$. What is the ...
7
votes
2answers
105 views

Why is one often requiring space constructibility in Savitch's theorem?

When Savitch's famous theorem is stated, one often sees the requirement that $S(n)$ be space constructible (interestingly, it is omitted in Wikipedia). My simple question is: Why do we need this? I ...
2
votes
2answers
114 views

Why does a polynomial-time language have a polynomial-sized circuit?

I wish to understand why P is a subset of PSCPACE, that is why a polynomial-time langauge does have a polynomial-sized circuit. I read many proofs like this one here on page 2-3, but all the proofs ...
-1
votes
1answer
111 views

Relationship between L and PSPACE

I have a question have to answer, so that, if anyone have the answer, please help me. The problem is: Give a self-contained proof that $\mathsf{L} \neq \mathsf{PSPACE}$ where: $\qquad \mathsf{L} ...
-1
votes
1answer
456 views

Book to learn Algorithm Complexity

I need a good book which starts from quite beginner to learn about calculating the complexity of Algorithm??
1
vote
2answers
64 views

Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete. Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
1
vote
1answer
54 views

Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
7
votes
1answer
93 views

Does $\mathsf{NSPACE}( f (n)) = \mathsf{coNSPACE}( f (n))$ hold for $ f(n) < \log (n) $?

It's known that for $f(n) \geq \log n$, $\mathsf{NSPACE}(f(n)) = \mathsf{coNSPACE}(f(n))$. What if $f(n)<\log n$? Are they also equal?
5
votes
1answer
93 views

NL- definition and a problem

The question is: What is the smallest complexity class in which the following problem is contained: Given a graph with $n$ nodes, Is there independent set of size of at least $n-10$? I have a little ...
6
votes
1answer
313 views

Bit complexity of O(1) time range query in a $k$-ary array

Consider the following problem: Let $k$ be a constant. We are given a $k$-ary array $A_{d_1\times\ldots\times d_k}$ of $0$ and $1$'s. Let $N = \prod_{i=1}^k d_i$. We want to create a data structure ...
2
votes
1answer
84 views

Bipartite Problem is Log-Space Reducible To $s$-$t$ Undirected Connectivity

Prove that the problem of determining if graph is bipartite is computationally equivalent under log-space reductions to $s$-$t$ undirected connectivity. Problem of $s$-$t$ undirected connectivity is ...
2
votes
0answers
182 views

Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
5
votes
1answer
200 views

Are there strongly-polynomial algorithms that take more than polynomial time?

In [1] strongly-polynomial is defined as either: The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic ...
2
votes
1answer
91 views

Power of Double - Logarithmic Space

I try to solve exercise "on the power of double - logarithmic space" from the great textbook Computational Complexity by Oded Goldreich. The goal is to show that the given set $S=\left \{ w_k \mid k ...
2
votes
1answer
61 views

Concluding $SPACE(n^2) \neq SPACE(n^7)$ from universal turing machine running time

Let $M_U$ be an universal Turing machine which fulfills the following condition: If $M$ running $x$ takes $f(x)$ space, then $M_U$ running on $\langle \langle M\rangle,x\rangle$ takes ...
3
votes
1answer
121 views

Equality of NSpace and coNSpace classes

I'm trying to decide which of the following statements are true: $\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$ $\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$ ...
5
votes
2answers
280 views

Space complexity below $\log\log$

Show that for $l(n) = \log \log n$, it holds that $\text{DSPACE}(o(l)) = \text{DSPACE}(O(1))$. It's well known fact in Space Complexity, but how to show it explicitly?