Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

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

Delete consecutive characters and add zeros at the end with a restriction

Given an array of characters, I need to delete all the characters that got repeated 3 or more times (consecutively) and add '0' at the end of the array for every deleted character, The restrictions: $...
user avatar
  • 21
0 votes
1 answer
30 views

Difficulty understanding the CANYIELD function in the Sipser text's proof of Savitch’s theorem

I was wondering whether someone could help me resolve an issue I have understanding the proof given for Savitch’s theorem in the Sipser text (3rd edition). The question I have is more or less ...
user avatar
  • 51
0 votes
0 answers
21 views

The total number of nodes and the height of a ternary search tree

So I need to insert into the ternary search tree (TST) about N strings. Each string is a unique ID "consists of 10 letters, the first 3 are upper case letters and the last 7 are digits" for ...
user avatar
1 vote
1 answer
39 views

Implications of Savitch's theorem

I'm trying to figure out if the following statements are true: • Savitch’s theorem implies that $NSpace(\log n)$ = $DSpace(\log n)$. • Savitch’s theorem implies that $NSpace(n^2)$ = $DSpace(n^4)$. • ...
user avatar
1 vote
0 answers
14 views

example of an NL-completeness reduction?

I'm looking for simple examples of nondeterministic log-space completeness reductions. In particular I seem unable to construct any nontrivial widget using 2-SAT clauses, which is known to be NL-...
user avatar
1 vote
1 answer
89 views

Breakdown of the Space Hierarchy Theorem

Say that we have two deterministic space complexity classes $SPACE(n^k)$ and $SPACE(f(n))$ where $f(n) = n^{k-1}$ when $n$ is odd and $f(n) = n^{k+1}$ when $n$ is even. Obviously, if $f(n)$ were ...
user avatar
  • 33
0 votes
0 answers
35 views

In search for a complete definition for write-only TMs / Tapes

In the following lines I will present my question, whose content is divided in two parts: Preparation and Actual . (1) — Preparation Regarding the formal definition of the (one tape) general Turing ...
user avatar
1 vote
2 answers
46 views

Space-efficient way to prove that a data has been processed before

Suppose that I have a stream of data packets in the form of unsigned 64 bit integers. And I want to make sure that I am not processing the same packet content more than once. A way of doing this would ...
user avatar
  • 11
0 votes
2 answers
83 views

Does creating a deep copy of a string of size N (in python) take space complexity O(N) or O(1)?

My question comes from solving this LeetCode question, in which we are given a string of characters with size N, and one of the solutions is to use a hashmap (dictionary in Python) to count the ...
user avatar
0 votes
1 answer
43 views

Do tasks that take up more memory/space always take more time?

Apologies if this is a trivial question - but I can't seem to find a direct answer to this. Say program A manipulates some data, and program B does the same manipulation, except it operates on a deep ...
user avatar
0 votes
0 answers
27 views

generate list of products from geometric sequences

Given lists of positive integers A = {1,a,a^2,a^3,..a^l} B = {1,b,b^2,b^3,..b^m} C = {1,c,c^2,c^3,..c^n} ... K = {1,k,k^2,k^3,...k^o} I want to make a list X, ...
user avatar
2 votes
1 answer
40 views

Is there a non PSPACE language s.t exponential padding of it is PSPACE?

I've had an exam in computational models a few days ago, and would like to check whether I made a mistake. The question goes like that: Is there a language $ L \notin PSPACE $ over the alphabet {0,1} ...
user avatar
  • 21
0 votes
2 answers
33 views

Are there any complexity classes that can be solved in Polynomial Time that are not in PSPACE?

These would be problems solvable in Polynomial time with and only with pseudo-polynomial or Exponential Space. Do such problems exist? if so which complexity class are they? If not can you prove that ...
user avatar
1 vote
0 answers
29 views

Graph based on strings of turing machine

For a $\Sigma$ with characters $0,1,$#$,\sigma_1,...,\sigma_m$. I have any $M$ that is a deterministic turing machine. Fix a $n$ (natural). i look at the following graph constructed from the turing ...
user avatar
1 vote
2 answers
110 views

How do I find out what SPACE a language has?

I want to know how I can calculate/find out which SPACE a language has, because I don't get it. I have this definition Definition: Fix a function $f: \mathbb N → \mathbb N$. We say that a language $A$...
user avatar
3 votes
1 answer
113 views

Is NL closed under complemenrt?

I am trying to understand if NL is closed under complement or not. By NL i mean the non-deterministic-logspace complexity. I suppose that the answer is linked to the fact that we don't even know if L =...
user avatar
4 votes
1 answer
445 views

What are the fundamentals of calculating space complexity in loops?

Imagine you loop n times, and every iteration you create a string of space n with scope only within that iteration (thus it is no longer accessible in the next iteration). I would look and say that I ...
user avatar
0 votes
1 answer
43 views

How do I determine the time and space complexity of the following algorithm?

I need to compute the time and space complexity in Big O notation for this algorithm I constructed for binary multiplication. ...
user avatar
0 votes
1 answer
75 views

Trivial Proof that EXP = PSPACE(im 99% sure i'm doing somthing wrong.)

Generalized chess is EXPTIME complete[1]. Generalized chess is also PSPACE complete[2]. Therefore $EXPTIME = PSPACE$. This implies that $P \neq PSPACE$ This proof is probably wrong. I want to know ...
user avatar
0 votes
1 answer
54 views

Randomized Algorithm Log-Space Exp-Time

I'm looking for an example of a randomized algorithm that halts with probability 1 (halts almost surely), uses only logarithmic space (worst case) and whose expected run time is not polynomial in the ...
user avatar
0 votes
1 answer
35 views

Help in proving L-Completeness

I'm trying to prove that the following language is L-complete A is a language where each word is comprised of 0s and 1s & the number of 0's is double that of the number of 1's So far I've managed ...
user avatar
  • 135
0 votes
0 answers
86 views

Space complexity for divide-and-conquer

Here's a simple question but I'm not sure there is a simple answer. This came up in an undergraduate algorithms class. Consider the following divide-and-conquer algorithm $A$ (here, $x_1, \ldots, x_n$ ...
user avatar
  • 101
1 vote
0 answers
23 views

N dimensional point, storage and access

Consider the case where you have 3-dimensional space. You want to know whether at a given point (x,y,z) in space, does anything exist(just like checking if in a 3D array at (x,y,z) is there a 1 or 0). ...
user avatar
  • 330
2 votes
1 answer
55 views

Is the language of PSPACE Turing Machines decidable?

Let $$L_{\text{PSPACE}}=\{\langle M\rangle : M \text{ is a TM using a polyspace amount of memory}\}$$ Is $L_{\text{PSPACE}}$ decidable? I don't think we can use Rice's Theorem because this doesn't ...
user avatar
  • 283
2 votes
0 answers
22 views

UCYCLE in LOGSPACE and linear time

Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it ...
user avatar
  • 121
2 votes
5 answers
469 views

Find two non-overlapping subarrays, with total sum equal to k

Given an array of N non-negative integers, and a number K, we need to find two non-overlapping contiguous subarrays that have a total sum of K. Our algorithm is supposed to find the minimum total ...
user avatar
  • 53
1 vote
1 answer
81 views

If a TM accepts a non-regular language, its space complexity is $\Omega(\log \log n)$

I have been given an assignment that I'm having a very hard time understanding. The assignment is to prove that if an algorithm accepts a non-regular language, the complexity is $\Omega(\log \log n)$ (...
user avatar
  • 13
1 vote
0 answers
20 views

Complexity classes and "local pre-processing"

My question I have two complexity classes, $L$ and $Mod_kL$. I'm confident these classes satisfy $L\subsetneq Mod_kL$, as I'll explain below but you can take for granted for a moment. From these two ...
user avatar
  • 131
0 votes
1 answer
32 views

Space complexity of Bubble sort

I have the following implementation of Bubble sort where it calls a helper method named swap. ...
user avatar
0 votes
0 answers
21 views

Where does this Oracle Problem belong in the Polynomial Hierarchy?

Given a problem $E_0$ such that: Any valid solution $S_0$ if there is any is of polynomial length. Assuming we are able to guess the solution $S_0$, for it to be valid: i. There are a fixed set of ...
user avatar
  • 703
1 vote
1 answer
80 views

Another version of Geography Game

The classic definition of normal “Geography Game” is the following: Each player on her turn choose a word such that starts with the last letter of the previously choosen word by another player. (...
user avatar
1 vote
2 answers
45 views

Does $P=NP$ require an algorithm that uses polynomial space?

if there was an algorithm that runs in polynomial time, but its size requires $O(2^n)$ bits, would that still prove $P=NP$?
user avatar
0 votes
0 answers
29 views

What is the complexity of (prime?) factorization with a fixed number of primes?

I was wondering what the complexity of factorization (on quantum computers or classical computers) is if we know that there must be exactly two prime numbers and we know the two prime numbers. For ...
user avatar
1 vote
1 answer
52 views

What is the space-complexity of the Newton-Raphson algorithm?

What's the space-complexity of Newton-Raphson? I think it reduces to the space-complexity of storing the inverse hessian matrix.
user avatar
  • 113
0 votes
1 answer
45 views

What is the true space-complexity of saving all divisors, because $N$ can have more divisors than the length of $N$?

$6983776800$ in binary has 33 bits but has $2034$ positive divisors. If a list of divisors were to be logarithmic in N, it needs to take less than 33 bits. I believe there is an infinite amount of ...
user avatar
1 vote
1 answer
145 views

Why does IP = PSPACE

Can anyone give an intuitive explanation to why IP = PSPACE, or at least one direction of it? I looked at many research papers but its very hard to understand the formalism unless you have a solid ...
user avatar
0 votes
0 answers
30 views

Is there such thing as average space complexity? If so, what is it for Timsort?

I was reading about Timsort's use in Python and wondered what the time and space complexities were which are dispalyed on the wikipedia page. The Wikipedia page lists average time complexity for ...
user avatar
0 votes
1 answer
89 views

Tic-Tac-Toe in PSPACE

Why is a game like Tic-Tac-Toe in PSPACE? For example for a nxn grid you have nxn! possible game tree paths (duplicates and illegal moves aside), then don't you need (n^2)! memory slots?
user avatar
2 votes
1 answer
59 views

Padding in proof of space hierarchy theorems

Referring to the Wikipedia proof : Wikipedia proves the space hierarchy theorem using the following language: $$ L = \{ (\langle M \rangle, 10^k) : \text{$M$ does not accept $(\langle M \rangle, 10^k)$...
user avatar
  • 137
3 votes
0 answers
59 views

Running time analysis of Savitch's algorithm

Savitch provided an algorithm which places NL in L^2 and hence the runtime of the algorithm is bound by $2^{O(\log^2n)}$. The runtime of the algorithm is not in P as NL is not known to be in SC. Is ...
user avatar
2 votes
1 answer
65 views

Ask for help to prove a inequality, thanks

Can anyone help to prove that $\sum\limits_{i=0}^{k-2}\log_2\left(\frac{n-i}{k-i-1}\right) > cn$ for some constant $c>0$? Here $k=\Big[\frac{n}{2\log_2 n}\Big]$ and $[x]$ denotes the integer ...
user avatar
2 votes
1 answer
66 views

$\log n$ lower bound for space complexity

I am currently reading Arora and Barak's Computational complexity. In Chapter 4 (Space complexity), they say the following: Since the TM's work tapes are separated from its input tape, it makes sense ...
user avatar
0 votes
1 answer
81 views

Can this recursive algorithm be converted to an iterative algorithm in O(1) space?

I am trying to convert this recursive algorithm ...
user avatar
0 votes
0 answers
40 views

Build a Turing machine to prove that a problem is $NL$

If we the language $A$, which is defined like this: $$A = \{\langle G,s,t \rangle \} \mid \text{ There is a maximum path in graph $G$ that begin in $s$} \} $$ I want to build a Turing Machine that ...
user avatar
0 votes
1 answer
101 views

Counting strongly connected components in a directed graph in $NL$

Define $K\_SCC = \{ \langle G, k \rangle \,:\, G \text{ has at least $k$ strongly connected components} \}$ I want to show that $K\_SCC \in NSPACE(\log n)$, using that $st-CONN$ and $\overline{st-CONN}...
user avatar
  • 1
2 votes
1 answer
70 views

Parts of a function used in Space Complexity

I'm finding contradictory information online where some places only consider auxiliary space and others define it as Space Complexity of an algorithm is total space taken by the algorithm with ...
user avatar
  • 145
4 votes
2 answers
413 views

Should the certificate for NPSPACE be polynomial in size?

There is a problem that I am working on. I have shown that the problem is NP Hard, but I haven't been able to show that it is in NP. But the problem is also known to be in EXP. My gut feeling is that ...
user avatar
0 votes
2 answers
107 views

Minimum number of moves puzzle

Let K players be among N towns in a circular position. On each turn, only one player can move. A player cannot move if he is the one who moved in the previous turn. A player can only move clockwise ...
user avatar
1 vote
1 answer
111 views

Find non common numbers in two arrays

Given two arrays of integers, please write a function that returns all elements present in one of the two arrays but not both. E.g. f([ 1, 3, 5 ], [ 1, 2, 4, 5 ]) -> [ 2, 3, 4 ] I know I can do ...
user avatar
  • 11
6 votes
0 answers
608 views

How to sort a queue using a temporary stack?

Suppose we have N natural numbers in a queue. ex queue = [3, 14, 1, 20] and an empty stack We are allowed to make only two actions: Action "x": Dequeue an element from the queue and push it ...
user avatar

1
2 3 4 5
10