Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
2
votes
2answers
505 views

non deterministic space hierarchy

I want to prove the non deterministic space hierarchy theorem. Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, Prove: $$NSPACE(f(n))\subsetneq NSPACE(g(n))$$ I ...
2
votes
0answers
35 views

Proving inexistence of a PCOMPLETE language in log logarithmic space cannot exist

Hello and thank you for helping me understand the following: I am trying to understand why the following cannot exist: A P-Complete language in regards to a log-logarithmic space. context: Defining ...
1
vote
0answers
20 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 ...
0
votes
1answer
23 views

How will I calculate the time and space complexity for this pyramid algo?

This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345": ...
2
votes
0answers
21 views

Existence of a P-Complete language with space($\log\log n$) reduction

I have been reading and searching and I still cannot understand if there exists a language as following: Can a language be P-complete with respect to $\mathsf{Space}(\log \log n)$ reductions? ...
3
votes
0answers
28 views

Understanding an example of an EXP-SPACE Problem

I am trying to understand the example given here of an EXP-SPACE time decision problem. They write : An example of an EXPSPACE-complete problem is the problem of recognizing whether two regular ...
0
votes
1answer
389 views

Create a binary search tree from a sorted array: Space complexity reasoning

Here is the Python code. The solution is fairly common and is seen in most textbooks like 'Cracking the Coding Interview' and 'Element of Programming Interviews'. ...
0
votes
1answer
60 views

Given a boolean matrix A of size n, A^p can be computed in space O(log n log p)

The solution to this problem can be found here. It says: To multiply $k$ matrices, we generate the result entry by entry, by running a counter $t$ and generating the $it$th entry in the product of ...
2
votes
1answer
51 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 ...
1
vote
1answer
168 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?
5
votes
2answers
149 views

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

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

Algorithm to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$

We have An array of $3n$ elements. we want to Find $x$ and $y$ for array of $3n$ numbers such that 1/3 are less than $x$. 1/3 between $x$ and $y$ and 1/3 greater than $y$. We can solve this problem of ...
0
votes
1answer
79 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 ...
1
vote
0answers
45 views

PSPACE-hardness of the unbounded puzzle

Given a board of size $n \times 1$ where $n=\infty$ (basically a tape, one way infinite), and a set of colors $C$, some starting color $c_{start} \in C$, a set of templates $T$ in a form $(c_k, i, c_i,...
3
votes
3answers
132 views

Does White never lose in Chess if Chess is solved?

If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?
1
vote
1answer
35 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....
1
vote
0answers
18 views

Showing that a directed graph that has a cycle belongs to NL [closed]

DCG = { G | Directed graphs that contains a cycle } How can I proof that DCG belongs to NL?
1
vote
1answer
26 views

The space complexity of a function that allocates space based on the input value and not size

What is the space complexity of the following hyphotetical function: void function(int n) { int[] array = new int[n]; // allocate array of size n return; } ...
1
vote
0answers
38 views

What is the complexity of finding e^(A) for a Hermitian matrix A?

If A is a hermitian matrix of size NxN .What is the order of no. of steps required to compute e^(A).How to prove it?
6
votes
3answers
1k views

Space complexity for storing integers in Python

So I was watching this mock interview by an Airbnb engineer on interviewing.io (https://youtu.be/cdCeU8DJvPM?t=1224) and around ~20:11 seconds he raises an interesting point. The question that the ...
0
votes
0answers
33 views

Why is $DSPACE(\log(n)) = NSPACE(\log(n))$ not known?

Here $DSPACE(\log(n))$ is the family of algorithms for which there exists a deterministic Turing machine using $O(\log(n))$ space. On the other hand $NSPACE(\log(n))$ is the family of algorithms for ...
1
vote
0answers
29 views

Is there any general, theoretical limit to time - space tradeoff?

In many algorithms, one can spot that improvements in time often are occupied by more memory requirements. For example usage of cache allows to speed up calculations by saving results in memory. Is ...
4
votes
1answer
57 views

Is the power of a natural number logspace-computable?

Given a constant $n\in\mathbb{N}_+$, is the simple power function $$ λ\,x\in\mathbb{N}_+.\,x^n $$ logspace computable by a logspace transducer (which has a read-only input tape, a working read-write ...
0
votes
0answers
33 views

Are polynomials in one variable logspace-computable?

Given a polynomial function $$p\quad=\quad \lambda\, x\in\mathbb{N}_0.\ \sum_{i=0}^n a_i x^i$$ with $a_i\in\mathbb{Z}$ for all $i\leqslant n$, can you compute $p$ by a logspace transducer if the input ...
3
votes
0answers
66 views

LogSpace reductions vs. PTime reductons for defining PSpace-completeness [closed]

Continuing Is every PSPACE-complete problem complete with respect to logspace reductions? : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. http://www.cs.cornell.edu/~kozen/...
5
votes
1answer
325 views

Is every PSPACE-complete problem complete with respect to logspace reductions?

A remarkable feature of the reduction showing that TQBF (True Quantified Boolean Formulas) is PSPACE-complete is that it actually runs in logspace, i.e. for any $A \in \mathsf{PSPACE}$, $$ A \le_L ...
2
votes
1answer
78 views

Is Space Complexity Always Less Than Or Equal To Time Complexity?

Background I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am ...
1
vote
1answer
65 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 ...
1
vote
1answer
891 views

Difference between auxiliary space v/s space complexity

I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$...
6
votes
2answers
1k views

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
1
vote
2answers
45 views

What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?

The first line of Sipser book for the Chapter- 'Time complexity', says that: Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the ...
4
votes
1answer
112 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
1answer
791 views

Fast, stable, almost in-place radix and merge sorts

I've developed LSD radix sort algorithm that is stable, about as fast as the classic LSD radix sort, require only $O(\sqrt{RN})$ extra space when we sort into R buckets. The same technique also ...
0
votes
0answers
157 views

Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
1
vote
1answer
34 views

Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
1
vote
1answer
65 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 ...
0
votes
1answer
57 views

Can you determinize an NFA in PSPACE?

QUESTION Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$? MORE DETAILS I'm asking this as I want to be able to ...
0
votes
1answer
51 views

TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The ...
0
votes
0answers
53 views

Logarithmic reduction from Clique to Half-Clique

so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises. I understand how to make a poly-reduction but I am not able ...
2
votes
1answer
306 views

Worst Case Space Complexity of Merge Sort and Bubble Sort

I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(...
0
votes
0answers
35 views

Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?

I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
2
votes
0answers
47 views

Is PSPACE vs NEXPTIME known?

I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME. Is anything known about ...
2
votes
1answer
835 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....
2
votes
1answer
265 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 ...
1
vote
2answers
97 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
3
votes
1answer
69 views

Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices. Thus, there are total nC2 or n(n-1)/2 such ...
1
vote
1answer
27 views

$NL^2 = NDSPACE(\log^2n)$ is closed under complement

From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement. From Immerman–Szelepcsényi theorem we have $NL = coNL$. Why then $NL^2 = coNL^2$
1
vote
1answer
19 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$...
1
vote
0answers
32 views

Space(n) and Space(n^2) implications

I've a problem where I have to prove the following statements: (i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$ (ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$ For the Space ...
2
votes
1answer
33 views

NL-Hardness of Target

When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve: $ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...

1 2 3 4 5 7