# Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

445 questions
Filter by
Sorted by
Tagged with
17 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 ...
240 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 ...
54 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)$ (...
17 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 ...
31 views

### Space complexity of Bubble sort

I have the following implementation of Bubble sort where it calls a helper method named swap. ...
17 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 ...
70 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. (...
41 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$?
28 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 ...
39 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.
44 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 ...
90 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 ...
30 views

64 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?
29 views