# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

426 questions
Filter by
Sorted by
Tagged with
1answer
459 views

### Complexity of simplifying two-variable algebraic expression

Given algebraic expression of two variables x and y, I want to simplify this algebraic expression until it cannot be simplified anymore. What algorithm can I use for this? For instance: x+x+y+y = 2&...
1answer
1k views

### Space and time complexity of balanced parentheses enumeration algorithm

Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string): A(prefix): If prefix ...
1answer
131 views

### Is HAMPATH in NL/L?

I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance ...
1answer
61 views

### IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why. First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a ...
1answer
78 views

### Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course ...
1answer
289 views

### How to prove strict space lower bounds using crossing sequences in Turing machines?

I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems? For example, suppose that you ...
1answer
81 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, ...
0answers
28 views

### Does this algorithm (least Hamiltonian path, checking vertex count, and no duplicates) decide Hamiltonian paths? If so, what is its space complexity?

Let G be a graph Suppose G has N vertices Let H be the ...
1answer
43 views

### Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell >n^2$. How can I with $2p$ passes over ...
1answer
38 views

### Can someone help me fully grasp idea and time/space complexity with this code?

My understanding is the following: Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
0answers
52 views

### Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
0answers
20 views

### Configuration of a space bounded turing machine

A configuration of a Turing machine is defined as the following: an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string on the tape, $q$ denotes the machine's current state, and $k$...
0answers
31 views

### Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
0answers
16 views

### What is the space-complexity of a boolean first-order query?

I have the intuitition that, if we implement a (space-efficient) boolean first-order query solver, the amount of consumed memory should depend on the data size (i.e., it should not be constant). ...
0answers
52 views

### Complexity in time and memory for graph search algorithm

I am working on an assignment where I have to write an algorithm to detect all vertices that lie in a cycle in a graph and then calculate its complexity. I have come up with an algorithm in pseudocode....
0answers
32 views

### A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
1answer
88 views

### $\text{DSPACE}(O(1))=\text{REG}$ Proof?

I want to know why $\text{DSPACE}(O(1))=\text{REG}$, especially in the direction of why all languages in $\text{DSPACE}(O(1))$ can be recognized by a finite automaton. I've thought for some time and ...
1answer
59 views

### Worst simultaneous blowup when converting to CNF and DNF

I know that converting between CNF and DNF produces an exponential blowup in size, but I would like to know which is the bound in size for a converted formula when one can choose between any of the ...
1answer
47 views

### The characterization of a problem as PSPACE-complete is …?

Let's assume that you found out that some problem $\mathit{\Pi}$ is PSPACE-complete (with respect to your favorite kind of reductions, say, logspace reductions). However, as there are dozens of well-...
0answers
31 views

### Storing a configuration of nondeterministec machines in log space

In Sipser's book page 351: Recall that Savitch's theorem shows that we can convert nondeterministic TMs to deterministic TMs and increase the space complexity $f(n)$ by only a squaring, provided ...
0answers
50 views

0answers
25 views

### Without using the Space Hierarchy Theorm is there any other way to prove that NL is not equal to PSPACE

From what I know there is no alternate way that NL is not equal to PSPACE. If possible can you link a paper or some book recommendations to show that this is the case. Thank You Akash
0answers
93 views

### If problem A is logspace reducible to 2-SAT, is A in NL?

I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL? If so, how does one ...
0answers
32 views

### How to check a graph diameter in LOGSPACE?

Given a graph G, how can I check that its diameter doesn't exceed log(n) (n is the number of vertices)- by using only O(log(n)) space? (adjacency matrix doesn't seems to help...)
0answers
42 views

### What does actually happens on tile hashing

I am going through Richard Sutton book about Reinforcement Learning and I just encountered the tile coding method. I understood pretty well the principles, however, at the very end of the section, ...
0answers
43 views

### EXPTIME $\neq$ EXPSPACE consequences?

We know that $EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE$, where $EXPSPACE = DSPACE(2^{poly(n)})$. Question: Is known any consequences of $EXPTIME \neq EXPSPACE$? (nothing in complexity zoo or wikipedia)
0answers
55 views

### Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
0answers
26 views

### United space-time complexity of finite strings

Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example ...
0answers
163 views

### Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching ...
0answers
141 views

### Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata  are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ...
0answers
479 views

### Is PSPACE closed under the following forall-there-exists construction?

Suppose I have a language $L$ (over alphabet $\Sigma$), such that $$w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w).$$ and I can give a turing machine that decides $P(x,y,w)$ ...
0answers
229 views

### Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$

Baker, Gill and Solovay  gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \...
0answers
40 views

### Naming for (memory near optimal) datastructres

Assume that we wish to solve some problem that has a information theoretic memory lower bound of $\mathcal B$ bits. In computer science, there are a few classes for data structures which are close to ...
0answers
128 views

### (Why) is there no complexity class for linear space (O(n))? [duplicate]

tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it? the Quantified Boolean Formula (QBF) problem is a P-space complete ...
0answers
647 views

### Space Complexity

This particular code is written in C. ...
0answers
187 views

### Parallel time is sequential space

Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, the ...
0answers
528 views

### Examples of real world graphs that are too big for a single commodity-type machine

I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence ...
1answer
175 views

### How to show that FPATH is in NL?

Consider this problem: $\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$ It's allowed to visit nodes outside ...
1answer
72 views

### Local and Global storage with multithreading pools + locking threads

I am having difficulty answering the following questions relating to the use of threading. Question 1 is of relating to the possibility of a local storage per thread and a global storage accessible ...
0answers
120 views

### General object recognition versus specific object recognition

I have a question about the difference between general object detectors and specific object detectors. By specific object detectors, I'm referring to classifiers/object recognizers that are built to ...
0answers
480 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 ...
1answer
142 views

### Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says: Let $L\in NPSPACE$. Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that ...
1answer
229 views

### Show that problem is PSPACE-complete - path in directed graph

I have a following problem: Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...