# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

387 questions
Filter by
Sorted by
Tagged with
792 views

### Do regular languages belong to Space(1)?

I was wondering, if we take some regular language, will it be in Space(1)? For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language. ...
264 views

### Is Not-STCON is NL-Complete?

$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$ I've tried the following proof: Let $S\in NL$, and ...
106 views

### PSPACE-completeness of DFA intersection problem

Let some deterministic finite automata be given. There is a problem of determining whether the intersection of these DFA is empty, and I want to show its PSPACE-completeness. It seems to me that I ...
47 views

### In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?

In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex ...
758 views

### Prove that $L$ is closed under Kleene star iff $L=NL$

Prove that $L$ is closed under Kleene star iff $L=NL$ Hi, I am trying to solve this exercise, but it is quiet difficult. Of course first part is very easy: Let assume that $L=NL$. Lets consider ...
292 views

### Does graph connectivity being NP-complete imply NL=P?

I asked this question on cstheory.se before, where someone pointed out that it is equivalent to asking whether P=NP implies NL=P (thus I edited the question accordingly). However, my supervisor ...
466 views

92 views

71 views

### what will be space complexity for snippet for(i=1 to n) int x=10;?

The space complexity of the code snippet given below: ...
51 views

### Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
64 views

### Logarithmic space verifier with unbounded witness

this is a HW question, but its considered a bonus question so I'd appreciate a direction. Definitions: The actual question: **Images taken from HW in TAU Complexity course by Amnon Ta-Shma. My ...
576 views

### Sorting an array of strings by length in linear complexity

I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using ...
48 views

### Exponential Space Complexity equality

Consider $$\bigcup_{c \in \mathbb{N}} \mathsf{DSPACE}(2^{c (\log{n})^2}) \quad \overset{?}{=} \quad \bigcup_{c \in \mathbb{N}} \mathsf{DSPACE} ( n^{c \log{n}})$$ My lecture notes say that this is ...
91 views

105 views

### Why do we set conditions f(n) ā„ n resp. f(n) ā„ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$). Why do we have these ...
450 views

### Certificate Definition of NL

As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for ...
168 views

### How to denote the space complexity in terms of output

Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage ...
484 views

### Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
349 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 ...
896 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 ...
158 views

967 views

### Is Breadth First Search Space Complexity on a Grid different?

Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning: For example, the flood fill question is described here: https://www....
695 views

### Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
317 views

### Relation beetween log-space reduction and polynomial time reduction

I read somewhere that given two languages A and B, if A <=(log) B, then A <=(P) B (with <=(log) the log-space reduction and <=(P) the polynomial time reduction), but I'm not sure about the ...
157 views

### Space complexity of boolean circuit evaluation

I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size. Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$. Now, assuming the fan in of ...
986 views

### STCON is NL complete - but why is the reduction in L?

I saw the proof for STCON being NL complete here : https://en.wikipedia.org/wiki/St-connectivity I understand the reduction, but how is it logspace? I understand each state is of $O(\log(n))$ space....
50 views

### Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC

Lets consider $$ACYCLIC = \{\langle G \rangle | G \text{ is acyclic}\}$$ We are going to prove that $ACYCLIC\in NL$. I know that the easiest approach for this task is to use the fact that $coNL=NL$. ...
425 views

### Space requirement of a universal Turing machine

Given a representation $g$ (e.g. the GĆ¶del number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$. If $B$ is restricted to using at most $n$ memory cells of its tape and the ...
58 views

### Replacing n with 2n in asymptotic bounds

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
171 views

### Time complexity of minimizing Boolean expression

Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used. The following Wikipedia article ...
91 views

### Can a cellular automata structure simulates another cellular automata structure?

In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure? Is there a category for this ...
83 views

### Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
669 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)$ ...