# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

324 questions
Filter by
Sorted by
Tagged with
205 views

### Why is the complement of SAT in IP?

It is mentioned in Sipser's text that the complement of SAT is in $IP$, before $IP$ is formally introduced. After looking at the definition and some of the results, I still don't see why this is the ...
2k views

319 views

### What is the big-O (worst-case upper bound) for time and space requirement of the different Chomsky classes?

Everybody knows the Chomsky-hierarchy for describing formal languages and big-O notation for describing time and space complexity of a function. We know, that each class in the Chomsky-hierarchy ...
1k 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 ...
336 views

### Is L closed under linear-time reductions?

L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace. Is L closed under linear-time reductions? It is ...
153 views

### Space-unconstructable function in the proof of Savitch's theorem

I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it. The proof I'm talking about is the same as is currently on ...
850 views

### Is this in-place merge algorithm efficient or not?

I have trouble analyzing the characteristics of this algorithm that merges two adjacent sorted lists. Basically it looks at some number of the tail of the first list, and the same number of head ...
716 views

### Expected space consumption of skip lists

What is the expected space used by the skip list after inserting $n$ elements? I expect that in the worst case the space consumption may grow indeﬁnitely. Wikipedia says space $O(n)$. How can this ...
1k views

### Relation between interactive proof systems (IP), NP, coNP, PSPACE

I would like to ask you some clarification on the following question: know that ${\sf NP}$ is a subset of ${\sf IP}$ and also ${\sf coNP}$ it is a subset of ${\sf IP}$. So ${\sf IP}$ is a biggest ...
104 views

### Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?

My recent question on Programming Puzzles and Code Golf got some fair attention and showed that not only it is very easy to output $10^{100}$ symbols and halt, but actually quite convenient in many ...
390 views

### space complexity of DFA intersection problem

the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper ...
797 views

### Checking whether a digraph on $n$ vertices contains exactly $10\sqrt{n}$ strongly connected components in NL

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 exactly ...
298 views

### What's after EXPSPACE?

As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE. Thinking about this question, I came up with a ...
134 views

### Non-existence of PSPACE-hard unary language

I'm trying to prove that unless $\mathsf{P}=\mathsf{PSPACE}$, there is no unary language which is $\mathsf{PSPACE}$-hard. Assuming there is an unary language $A$ which is $\mathsf{PSPACE}$-hard, it ...
99 views

270 views

### Space complexity of statistic functions

When computing statistics on a list of data it occurred to me that most of the standard statistic functions, such as mean, min, max can be computed in O(N) time with O(1) space. They can also be ...
99 views

### Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
625 views

### TM - reject definition and complement

I have couple of questions about Turing machines: What is the definition of the "reject" state in TM? If the input was very small and, after one step, the machine gets to the end of the input, but it ...
544 views

241 views

### What if there is a polynomial-time algorithm to minimize NFA?

Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?
218 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 ...
797 views

### Why is the set of NFA that accept all words in co-NPSPACE?

In Sipser's book there is a section describing how to decide $\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$ in polynomial space. ...
320 views

### Show that k-clique lies in L

The following exercise is difficult for me: Show that for each $k \in \mathbb{N}$ the question of existence of a $k$-clique within a graph lies in $\text{L}$. Hint: A $k$-clique denotes $k$ ...
664 views

### How to compare algorithms having the same complexity

I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same ...
298 views

### How is the space hierarchy theorem different for non space constructible functions?

Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem: if f(n) is a space constructible function then there are languages that can be ...
Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...