# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

404 questions
Filter by
Sorted by
Tagged with
276 views

### Why is DTIME(n) not equal to NP, and consequently, DSPACE(n) not equal to NP?

Intuitively it would seem like these equalities are false since DTIME(n) and DSPACE(N) are in terms of deterministic Turing machines and NP is non-deterministic, but I'm struggling to come up with a ...
54 views

### If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$?

We know that if $B$ is in $P$ and if $A \leq_p B$ then $A$ is in $P$ too. If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$? I think that the answer to this question is ...
556 views

### If A is NL-complete then complement of A is also NL-complete?

We know that coNL = NL. But, is this also true? If A is NL-complete then complement of A is also NL-complete? I don't see a reason for that it could be true.
203 views

### Any algorithm polynomial time with infinite space?

If I had an arbitrary amount of space at my disposal, couldn't I vectorize/parallelize any program in such a way that it would only need one step? For example, I could let my CPU have an inbuilt look-...
100 views

### Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)

There is given input - words is sequence of numbers: $w_i$ is number in sequence, $i$ is position. All of them are in written in binary system. $$w_1\#,...\#w_k\#i$$ Prove that there ...
121 views

### Confusing method of proving PSPACE-completness

I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me: We consider sequence (of polynomial length) of ...
152 views

### Demonstration that EXP is closed under union complementation and concatenation

How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?
868 views

### Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
226 views

### PSPACE languages reducible to other PSPACE languages in polynomial space

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?
96 views

### Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$

I need help with the following: Let $k\in \mathbb{N}$, define: $L^k=DSPACE(O(log^k(n)))$ $NL^k=NSPACE(O(log^k(n)))$ and: $PolyL=\bigcup_{k=1}^{\infty}L^k$ $PolyNL=\bigcup_{k=1}^{\infty}NL^k$ I need ...
173 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)$ ...
2k views

30 views

### Does checking the middle bit of an input require a log(n) space pointer? (Reusing space)

Let n be an even integer. Let I be an input of length n. Positions start at 0: the first ...
51 views

### Is $L \subset 1NL$ when $L \neq NL$? [closed]

A log-space Turing machine has a read-only input tape, a write-only output tape and uses at most $O(\log n)$ space in its read-write work tapes. The classes $L$ and $NL$ contain those languages which ...
36 views

### Space efficient representation of Regular graphs

Let $G$ be a $k$-regular graph (each vertex have a degreee $k$). It is trivial to store the graph in $O(\log n)$ space or words such that $j$th neighbour of any vertex can be found in $O(\log n)$ time....
153 views

### Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space reductions ...
78 views

### How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
27 views

### Complexity and hardness of undirected path

Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$...
254 views

### How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
40 views

### Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the ...
405 views

### Show that $A_\mathrm{LBA}$ is PSPACE-Complete?

I want to show that $A_\mathrm{LBA}$ is PSPACE-Compelte. Say we proved it is in PSPACE. Now for PSPACE-HARD: I had an idea, which was very similar to some solution i found on the web- say we have a ...
365 views

### What is the Space Complexity of Tail Recursive Quicksort?

Looking at the following tail recursive quicksort pseudocode ...
69 views

### Understanding $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$

I'm having trouble understanding this statement: $DSPACE(s(n)) \subseteq DTIME(2^{O(s(n))})$. The logic is that $2^{O(s(n))}$ is the total number of different configurations a Turing Machine M that ...
455 views

### $MIN_{NFA}$ is PSPACE complete

The problem is taken out of Theory of Computational Complexity: Now, I think I've successfully proven that $ALL_{NFA} = \{(A) : A$ is an NFA and $L(A) = \Sigma^*\} \leq_p MIN_{NFA}$. Which implies ...
536 views

### What is a space constructible function?

I've searched this and was not able to understand the answer. What's the idea/intuition behind this? What's the purpose and why is it important? And considering the wikipedia explaination, ...
212 views

### Space/Time Hierarchy Theorem - proving the language of the machine is in the larger space class

I am trying to understand the space and time Hierarchy theorems according to Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach but the more general case. What I don't ...
572 views

### How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?

Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$ Prove that MULT $\in L$ How do I show that this language, MULT, is computable in Logarithmic space? Let us assume a#b#c ...
208 views

### Definition of space complexity when algorithm cycles.

I'm reading side by side my class notes and Papadimitrious' Computational Complexity book. At this point they are talking about space complexity. They give rules for computing space employed in an ...
268 views

### Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?

$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ There are two possible approaches to this exercise: Solving cycle in undirected graph in log ...
559 views

### Convert conjunctive normal form to equivalent boolean formula with only NAND gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with ...
410 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&...
921 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 ...
121 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 ...
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 ...
74 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 ...
283 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 ...
79 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, ...
31 views

### In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
63 views

### Indexing a huge dataset (that does not fit into central memory)

The problem. Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are ...
51 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 ...