Skip to main content
Computer Science

Questions tagged [space-complexity]

Ask Question

Asymptotic analyses of the space needed to run algorithms.

538 questions
Newest Active Bountied Unanswered
0 votes
0 answers
15 views

In Arora and Barak's book "Computational Complexity: A Modern Approach" (see draft pdf here https://theory.cs.princeton.edu/complexity/book.pdf), the $\mathtt{PATH}$ problem is given as the ...
synkathairo's user avatar
  • 1
0 votes
1 answer
56 views

I am trying to understand the complexity of a problem that involves solving some $\mathsf{PSPACE}$-complete problem exponentially many times. Namely, one can imagine $\Xi=\{\phi_1,\ldots,\phi_n\}$ to ...
Daniil Kozhemiachenko's user avatar
  • 165
0 votes
1 answer
60 views

It is known that BPL $\subseteq$ P where BPL is the class of languages that have a probabilistic Turing machine which decides input correctly with probability $\ge \frac{2}{3}$ and always halts ...
advocateofnone's user avatar
  • 3,413
2 votes
1 answer
94 views

Just want to check when you parallize Strassen's algorithm you get a time complexity of $O(\log n )$ because you divide and conquer $\log n$ times in parallel and a space complexity of $ O( n^{\...
user3133512's user avatar
  • 21
1 vote
1 answer
166 views

Given an array of unique elements of size $n$, the goal is to find the second maximum element using tournament tree method. The model of computation is RAM model. Algorithm: The idea to pair the ...
Rma's user avatar
  • 163
1 vote
1 answer
121 views

Given a rational value $x$ in binary and a value $k$ in unary, how much space in $|x|+k$ is needed to compute $\sin(x)$ to $k$ bits of precision?
user918212's user avatar
  • 341
0 votes
1 answer
102 views

Let $x \in \mathbb{Z}^+$ be an integer greater than or equal to two. Provided a binary presentation of $x$, do we have a lower bound or expected lower bound on the space required for any Turing ...
user918212's user avatar
  • 341
0 votes
0 answers
36 views

This is an algorithmic challenge from the factory game Shapez2, essential for building what's known as a TMAM (True Make Anything Machine). I’ve been researching this problem over the past month. ...
rone D's user avatar
  • 1
2 votes
1 answer
528 views

I have written a proof of the statement $\sf P = NL \neq NP$. However, since the proof for the first part is quite simple, I suspect that it may be incorrect. I would appreciate it if you could help ...
Mohsen Ghorbani's user avatar
  • 563
0 votes
1 answer
78 views

$$\text{SIMPCYCLE}=\{\langle G,d\rangle: G \text{ has simple cycle of length at most } d \}$$ I need to show that $\text{SIMPCYCLE}$ is in NL. We know that simple cycle means no repeated vertices ...
Monte_carlo's user avatar
  • 97
1 vote
2 answers
104 views

I'm trying to analyze the space complexity of the following recursive function: def f(s): if s == "": return f(s[1:]) The function takes ...
christain's user avatar
  • 11
1 vote
0 answers
52 views

I was going through some online lecture notes, which have the following claim: If it takes space $s_1(n) \ge \log n$ to compute $f$ and space $s_2(n) \ge \log n$ to compute $g$, then one can compute ...
advocateofnone's user avatar
  • 3,413
0 votes
0 answers
54 views

I have come across this question: Assume $\text{DSPACE}(n^2) \subseteq \text{DTIME}(n^{\lg n})$. What is the most precise conclusion? $\text{DSPACE}(n^6) \subseteq \text{DTIME}(n^{2\lg n})$ $\text{...
GreekMustard's user avatar
  • 1
0 votes
0 answers
72 views

Let $$L=\left\{\,\langle\,B_n,\, \,x\,\rangle:\enspace\substack{B_n \text{ is a boolean circuit and } \\x \in \{0, 1\}^n\text{such that }B_n(x) = 1}\right\}$$ I want to prove that $L$ is $\textbf{P}$-...
Rio's user avatar
  • 1
2 votes
1 answer
194 views

A leveled graph is directed graph where the vertices are divided into sets $A_1 ,...,A_k$ called "levels", and only edges from one level to the next higher level are permitted. $DPATH=\left \...
Daniel's user avatar
  • 341

15 30 50 per page
1
2 3 4 5
…
36