Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
0
votes
0answers
23 views

Is $DSPACE(n^8) \subset NSPACE(n^5)$?

I encountered this problem which asks whether $DSPACE(n^8) \subset NSPACE(n^5)$ is sure to hold. I know from Savitch's Theorem that: $$ NSPACE(n^5) \subseteq DSPACE((n^5)^2) = DSPACE(n^{10})$$ If the ...
0
votes
1answer
25 views

Is NSPACE(2^O(n)) = NSPACE(n^2 * 2^(O(n))

As said in the title, i am quite curious wether NSPACE(2^(O(n)) equals NSPACE(n^2 * 2^(O(n)) I am aware of the fact, that NSPACE(k * 2^O(n)) equals NSPACE(2^O(n)) due to linear space reduction (i.e. ...
1
vote
0answers
12 views

Configurations and CNF formula for neighboring configuration

A configuration of a Turing machine $M$ which runs in space $S(n)$ contains the state, the head positions, and the content of non-blank cells of all the tapes. For $M$ and an input $x$, we define its ...
0
votes
2answers
45 views

Analyzing space complexity of passing data to function by reference

I have some difficulties with understanding the space complexity of the following algorithm. I've solved this problem subsets on leetcode. I understand why solutions' space complexity would be O(N * 2^...
2
votes
1answer
47 views

Uniform Hashing. Understanding space occupancy and choice of functions

I'm having troubles understanding two things from some notes about Uniform Hashing. Here's the copy-pasted part of the notes: Let us first argue by a counting argument why the uniformity property, we ...
0
votes
1answer
11 views

one for loop wraps 2 indexof method, what is the time efficiency?

I'm confused about how to know the time / space efficiency. If there is an array whose size is n, do a for loop on this array, so that time efficiency should be O(...
0
votes
0answers
17 views

proof that $NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$

I came across this problem which asks to prove: $$NSPACE(S(n)) \subseteq DTIME(c^{S(n)})$$ for $S(n) \geq \log{(n)}$, with $S(n)$ being fully time-constructible... As an attempt, isn't the proof ...
1
vote
1answer
14 views

Is $NSPACE(S(n)) \subseteq DSPACE(S(n))$ if $S(n)$ is time-constructible?

I read from Savitch's theorem that given a fully space-constructible function $S(n)$, we have $$ NSPACE(S(n)) \subseteq DSPACE(S(n)^2) $$ Am wondering, what happens if $S(n)$ is fully time-...
1
vote
1answer
86 views

Is every linear language in NL?

I wonder if all the linear languages are in NL? I was thinking that we can take an input-language $L$ and convert it to linear normal form. If this is not possible, the machine rejects. If the ...
0
votes
0answers
24 views

Does this algorithm traverse trees in logspace?

Does this algorithm traverse trees (correctly) in logspace? Background: Assume each vertex is expressed as an integer. A vertex is larger than another if the corresponding integer is larger. A tree ...
0
votes
0answers
41 views

Prove that all regular language is in L

im looking for a formal proof to demonstrate that all regular language is in L (logarithmic space). I deduced that all regular languages has a DFA that accept them, so if i find a way to transform all ...
0
votes
1answer
32 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 ...
2
votes
2answers
43 views

Logarithmic space verifier with unbounded witness

this is a HW question, but its considered a bonus question so I'd appreciate a direction. Definitions: The actual question: **Images taken from HW in TAU Complexity course by Amnon Ta-Shma. My ...
1
vote
1answer
18 views

Log space reduction from STCONN to CYCLE

I read this post: Showing Cycle is NL-complete?, but I am not sure why the reduction is log space, as it requires keeping track of the new graph, which has $n^2$ nodes.
1
vote
1answer
37 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 ...
1
vote
1answer
18 views

Importance of space constructability in time space relation in complexity

I am reading Arora-Barak's Complexity book. In Chapter 4, they state and prove the following theorem. Why $S$ should be space constructible? Wouldn't all three containments of theorem hold, even if $...
0
votes
1answer
42 views

Efficient algorithm to compare arrays problem

I was submitted an interesting problem, but I wasn't able to find a solution. Define a function p(x, y) that takes int x and y, with ...
1
vote
1answer
27 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 ...
0
votes
1answer
19 views

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

Let n be an even integer. Let i be an input of length n. Positions start at 0: the first ...
0
votes
0answers
19 views

Does this imply Hamiltonian path cannot be decided in nondeterministic logspace?

Suppose I nondeterministically walk around in a graph with n vertices. When looking for a Hamiltonian path, at some point I’ve walked n/2 vertices. There are (n choose n/2) different combinations of ...
0
votes
1answer
26 views

Can uniqueness of strings (each with an equal number of 1's and 0's) be decided in logspace?

Let k be a positive even integer. Given a list of (k choose k/2) k-sequences, each with an ...
0
votes
0answers
31 views

Does this imply checking a candidate Hamiltonian Path solution can be done in logspace?

Assume vertices are integers base 2. Smallest vertex is 1. There are n vertices. Our input is: the number of vertices (n expressed in log(n) bits - ...
1
vote
1answer
24 views

Lower bound time complexity for obtaining an arbitrary entry in a hashtable

I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable, the algorithm should return a pointer to an arbitrary nonempty entry in the ...
1
vote
1answer
14 views

Big O notation space/time

I realize that each time I have to deal with the Big-O notation I am questioning myself why complexity in time or space share the same formal notation/letter. It is always confusing when I read ...
4
votes
2answers
51 views

Does time or space complexity of arithmetic operations get affected by the number of digits?

Suppose I have two 5-digit numbers (A and B) and two 50-digit numbers(C and D). Do the operations A+B and C+D have equal complexity in terms of time and space? or C+D is more complex due to the size ...
0
votes
1answer
40 views

Find nearest neighbour in a radius

I have a set of points A in my space (geo points but I can assume they are on a 2D plane). I have another set of points B. For every point in B I want to find every point in A inside a radius R with ...
-1
votes
1answer
64 views

The existence of a cycle in a directed graph is a NL-complete? [duplicate]

Show that the problem of the existence of a cycle in a directed graph is a $NL-complete$ problem. I have already successfully demonstrated that this problem $\in NL$. But I'm stuck on how to take it ...
1
vote
1answer
59 views

Nondeterministic Logarithmic-space in directed graph

I continue to learn the complexity myself, currently I am interested in the complexity of space. I have read several books and tried some exercises as a practice. I would like to have your idea on the ...
1
vote
2answers
226 views

Logspace algorithm for balanced parentheses problem

Currently I want to learn the complexity of space, I read a few of the books on it. On this I encountered this example problem. I would just like to know how to show that the following problem $​\in L ...
2
votes
1answer
33 views

Algorithmic problem with many different time/space complexity solutions

I am preparing a lesson about algorithmic thinking for beginner programmers. I would like to show them an easy to understand problem which has as many solutions as possible with different time or ...
4
votes
1answer
80 views

Query: Given a graph, is edge x in an optimal TSP tour?

Consider the decision problem that when given a graph, we need to decide if a particular edge belongs to any optimal solution to the traveling salesman problem on that graph. It may be argued that ...
1
vote
1answer
274 views

Space complexity of Travelling Salesman Problem

I am having trouble coming up with the space complexity of the TSP algorithm. https://www.geeksforgeeks.org/travelling-salesman-problem-set-1/ To me the space complexity for the brute force is the ...
1
vote
1answer
41 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 ...
2
votes
1answer
72 views

Time complexity for the 'Restore IP Addresses' problem

There's a programming problem 'Restore IP Addresses' where given a string containing only digits, restore it by returning all possible valid IP address combinations. Example, "25525511135" returns ["...
1
vote
1answer
42 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-...
3
votes
1answer
125 views

Composition of functions computable in logspace

The bit-graph of $f\colon \{0,1\}^* \rightarrow \{0,1\}^*$ is the language: $\text{BIT}_f := \{\langle x,i \rangle : 1\leq i \leq|f(x)| \text{ and the $i$-th bit of } f(x) \text{ is } 1\}$ It is ...
1
vote
0answers
23 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 ...
2
votes
0answers
36 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 ...
0
votes
1answer
27 views

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

This is an algo. programmed for displaying a letter pyramid if the buildPyramids() method is passed argument str, i.e. "12345": ...
2
votes
0answers
24 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
39 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 ...
2
votes
1answer
97 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 ...
0
votes
0answers
31 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 ...
1
vote
0answers
46 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,...
0
votes
1answer
68 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 ...
3
votes
3answers
141 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
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
28 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
41 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 ...

1
2 3 4 5
8