Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
5
votes
1answer
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 ...
5
votes
1answer
2k views

Minimum space needed to sort a stream of integers

This question has gotten a lot of attention on SO: Sorting 1 million 8-digit numbers in 1MB of RAM The problem is to sort a stream of 1 million 8-digit numbers (integers in the range $[0,\: 99\...
5
votes
1answer
128 views

Complexity of space density and sequentiality

I'm looking for some standard terminology, metrics and/or applications of the consideration of density and sequentiality of algorithms. When we measure algorithms we tend to give the big-Oh notation ...
5
votes
1answer
450 views

Why is CVAL a P-Complete problem?

We've learned in class that CVAL is P-complete. CVAL is the language of all $\langle C,x\rangle$ where $C$ is a formula (a circuit which outputs $0$ or $1$) and $x$ is some input for $C$ such that $C(...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
1answer
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 ...
5
votes
0answers
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 ...
4
votes
2answers
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 indefinitely. Wikipedia says space $O(n)$. How can this ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
1answer
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 ...
4
votes
2answers
99 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following langugae is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
4
votes
1answer
170 views

$UCYCLE$ is in $L$

I'm trying to understand the log-space algorithm for $$UCYCLE = \{ \langle G \rangle \ | \text{ $G$ is an undirected graph containing a cycle} \}$$ The basic idea is traversing from every $v\in V$, ...
4
votes
2answers
143 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 ...
4
votes
2answers
198 views

Show that the multiplication lies in FL

I don't know exactly how to solve the exercise below. Show that the multiplication lies in $\text{FL}$. Hint: A useful approach to a solution is to split the exercise into two parts and to ...
4
votes
1answer
137 views

Why not polynomial-space reductions for $PSPACE$-hardness?

A language $L'$ is $PSPACE$-hard if for every $L \in PSPACE$ we have $L \le_p L'$. Here $L \le_p L'$ means that $L$ is polynomial-time reducible to $L'$. Why does we use time reductions instead of ...
4
votes
2answers
382 views

NSPACE for checking if two graphs are isomorphic

I was studying nondeterministic Turing Machines and came across the following question: Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are ...
4
votes
1answer
822 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 ...
4
votes
2answers
988 views

Time complexity for count-change procedure in SICP

In famous Structure and Interretation of Computer Programs, there is an exercise (1.14), that asks for the time complexity of the following algorithm - in Scheme - for counting change (the problem ...
4
votes
1answer
154 views

Problem with understanding proof of the Space Hierarchy Theorem

The Space Hierarchy Theorem states that If $f(n)$ is space contructible, then for any $g(n) \in o(f(n))$ we have $SPACE(f(n)) \neq SPACE(g(n))$ An example of a SHT proof can be found here or here ...
4
votes
1answer
469 views

Median-of-medians in O(log n) memory

Is there a way to use median-of-medians to find a median in, simultaneously, ​ ​O(log n) ​ ​memory and O(n) comparisons? The user orlp on this site seems to claim that there is. Getting ​ ​O(log n) ...
4
votes
1answer
63 views

Acceptance behavior of L and NL with and without cycling

The complexity class NL seems to allow cycling, otherwise we wouldn't have SL $\subset$ NL. What about L? If an algorithm from L cycles for a given input, it certainly cannot accept (because it won't ...
4
votes
1answer
434 views

Lower space bound on a turing machine accepting palindromes

Let $$ PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace $$ How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$? I have a feeling that I need to use ...
4
votes
0answers
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 ...
4
votes
1answer
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 ...
3
votes
3answers
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 ...
3
votes
1answer
544 views

Proving that NPSPACE $\subseteq$ EXPTIME

I am following "Introduction to the theory of computation" by Sipser. My question is about relationship of different classes which is present in Chapter 8.2. The Class PSPACE. $P \subseteq NP \...
3
votes
1answer
729 views

is Co-NP in PSPACE?

Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.
3
votes
1answer
672 views

Why is PH in PSPACE?

$PH \subseteq PSPACE$. In order to prove it, one has to show that for a language $A \in \Sigma_k$ (for some $k \in \mathbb{N}$) there exists a turing machine $M_A$ that decides it in polynomial space....
3
votes
2answers
154 views

Which graph algorithm should I use?

I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time ...
3
votes
2answers
909 views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
3
votes
1answer
2k views

Prerequisites of computational complexity theory

what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical ...
3
votes
2answers
305 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
3
votes
1answer
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?
3
votes
1answer
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 ...
3
votes
1answer
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. ...
3
votes
1answer
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$ ...
3
votes
2answers
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 ...
3
votes
1answer
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 ...
3
votes
1answer
476 views

L closed under logspace reduction

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 ...
3
votes
1answer
209 views

Finding dynamic programming algorithm

I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and $...
3
votes
1answer
1k 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 ...
3
votes
1answer
563 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 ...
3
votes
2answers
354 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 ...
3
votes
1answer
811 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 ...