Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
2
votes
1answer
17 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)$...
3
votes
0answers
30 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 ...
0
votes
1answer
34 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 ...
2
votes
1answer
25 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 ...
0
votes
1answer
69 views

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

I am trying to convert this recursive algorithm ...
1
vote
0answers
36 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 ...
0
votes
1answer
70 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}...
2
votes
1answer
22 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 ...
4
votes
2answers
309 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 ...
0
votes
2answers
80 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 ...
0
votes
1answer
56 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 ...
6
votes
0answers
193 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 ...
3
votes
1answer
37 views

Is there a way to study precisely the complexity with respect to the size of vertex set for some graph problem?

Suppose there is graph problem $L$ such that the instance $x$ of $L$ is a simple graph with $n$ vertices and $m$ edges. In the Turing machine model, we can encode a graph using $O(n^2)$ cells or $O((m+...
2
votes
2answers
57 views

Why can't one use the Cook-Levin theorem to show that TQBF is PSPACE-complete?

I have been reading Michael Sipser's Introduction to the Theory of Computation, and I have stumbled upon a paragraph in Chapter 8 (Theorem 8.9 on page 339 of the 3rd international edition) that I ...
1
vote
1answer
46 views

Check array in linear time with a constant space complexity

Given an array of integers I have to return true if all the elements in the array are different or all the elements are the same. Otherwise, I have to return false. E.g. ...
0
votes
0answers
26 views

Understanding the Space Hierarchy Theorem and its proof

This is what I've learned from the SHT and the sketch of its proof. I would appreciate pointing out any mistake. The intuition behind the Space Hierarchy Theorem is that "there are Turing ...
0
votes
1answer
29 views

Space complexity of a variant of st-connectivity

Consider a variant of STCON, called 2STCON, which is defined like this: $$2STCON = \{\langle G,u,v \rangle \} \mid \text{$G$ is a graph with } \mathit{two} \text{ paths from $u$ to $v$} \} $$ This ...
2
votes
0answers
87 views

How computationally hard are the battle systems of Paper Mario and Paper Mario: The Thousand Year Door?

What is the time complexity and space complexity of working out, in suitably generalised versions of the battle systems of both Paper Mario 64 and Paper Mario: The Thousand Year Door: The minimum ...
0
votes
1answer
58 views

Prove NLOGSPACE$\subset$PSPACE

Condidering the proof, NLOGSPACE$\subset$PSPACE I wrote following proof: NLOGSPACE = NSPACE$(\log n)$ $\hspace{15pt} \because$ Definition of NLOGSPACE NSPACE$(\log n)$ $\subseteq$ DSPACE$(\log^2 n)$ $\...
1
vote
0answers
29 views
0
votes
1answer
20 views

Big o notation for sublinear algorithm in streaming algorithm

Excuse me if this is obvious. At 1:55 of this Coursera video on streaming algorithms (see pasted image below for relevant slide), the professor mentions sublinear storage. I get the $N^{\alpha}$ but I ...
14
votes
0answers
131 views

What can be proven regarding the differences in power between unary ECMAScript regex functions and primitive recursive functions?

In 2014, inspired by Regex Golf, I started exploring, along with a mathematician going by the name teukon, what could be done in the unary domain in ECMAScript regex that went significantly beyond ...
1
vote
1answer
43 views

Randomized Version of NP

I came across interactive proofs and randomized computation, in particular, i read about the complexity classes $\text{IP}, \text{BPP}, \text{RP}$, etc. Since the above classes are well-known, I will ...
1
vote
1answer
43 views

Solving number of distinct elements in $O(\frac{n\ell}{p})$ space complexity with $2p$ passes over data

Suppose there is an n-element stream with elements from $\{0,1\}^\ell$ which means each element is in set $\{0, \dots , 2^\ell-1\}$. Also may assume $2^\ell >n^2$. How can I with $2p$ passes over ...
0
votes
0answers
17 views

What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution?

What will be a space complexity of a conversion of a sorted array to a balanced BST in case of a recursive solution? Could you, please, check my reasoning. Is it correct? Here is my algorithm for ...
1
vote
1answer
18 views

What is uniformity in Boolean circuits exactly?

I have two questions on Kaveh's answer to Definition of uniform boolean circuit : Kaveh mentions that the input is in unary encoding. In the definition it says the input is $1^n$, afaik $1^n$ is a ...
1
vote
1answer
38 views

Can someone help me fully grasp idea and time/space complexity with this code?

My understanding is the following: Time = With the initial not state is just to check if there are no elements in the list a. This is done in O(1) time. The first ...
1
vote
1answer
179 views

Can someone help me understand the time and space complexity?

Can anyone help me understand the time and space complexity here? I know zip() is O(1) and sorted() is O(n). The loop has the ...
0
votes
1answer
21 views

What are the guidelines/tips for calculating the complexity of a chained-recursive function?

Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions.. Are there any ...
8
votes
1answer
764 views

why does LSPACE(log space) complexity class exist but not logtime?

I noticed that in complexity classes, logspace class is defined but there is no logtime. I was wondering how is that possible? Normally, I would expect the opposite, It is possible to do a search ...
1
vote
1answer
60 views

Counting letter frequency in array in O(1) with hash function

I want to calculate the frequency of each character in an array. (e.g ['a', 'b', 'o', 'p'] There are several ways to do this: A Simple brute-force over the array would need $O(n^2)$ time and $O(n)$ ...
0
votes
0answers
39 views

In-place linear sort of integers, again

I am amazed by the many discussion regarding the existence of any linear and in-place sorting algorithm, and variants, see e.g. is-this-implementation-of-bucket-sort-considered-in-place is-counting-...
1
vote
1answer
73 views

Indexing a huge dataset (that does not fit into central memory)

The problem. Let us consider a huge file with billions of lines, each containing a string. There are $n$ different strings and $m$ lines in the file, with $m$ much greater than $n$, although both are ...
1
vote
0answers
52 views

Is it reasonable to assume modern computers can do hardware math with integers up to 2^64?

I was writing up an algorithm that involved knowing the size of integers my hardware can manage without having to resort to software implementations of math operations and the additional computational ...
0
votes
0answers
13 views

Inverse VR-Vision, theoretical possibilities and the additional requirements

When using VR-Vision for looking around and the vision is from some point of interest, the look-around is a rotation from inside that point and it reqires a record of a 360° photo or a 360° camera ...
2
votes
0answers
36 views

Space-Complexity of Van Eck's Sequence

What is the space-complexity of Van Eck's sequence? https://oeis.org/A181391 Input: $x$ (number in binary representation with $n$ bits) Output: $x$th number in Van Eck's sequence Length of input: $n$ ...
2
votes
1answer
60 views

Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$

Prove that $\mathsf{P} \neq \bigcup_{k=1}^{\infty}\mathsf{DSPACE}(\log^k n)$. Hint: Assume that there is an equality, show that this implies $\mathsf{DTIME}(n^{\log n})\subseteq \mathsf{P}$ via a ...
0
votes
1answer
59 views

How to find mean ,max ,min in constant time?

I was asked to be able to find minimum, maximum and mean of a large array in constant time. I used 3 variables to track these statistics and updated them on every insert operation. I don't feel like ...
0
votes
0answers
26 views

Composition on functions computable in logspace requires always inner recomputation?

We have a composition logspace computable functions where the outer machine is one-way and the inner is a logspace verifier with a read at once certificate tape and output string (instead of "yes&...
1
vote
1answer
319 views

Show linear bounded automata accepting w is PSPACE-complete

ALBA={⟨M;w⟩ | M is linear bounded automata which accepts input w} Show that ALBA is PSPACE-complete. How I would try to solve it... We need to prove ALBA belongs ...
1
vote
2answers
135 views

Store a n-bit string using only O(log n) space

Is it possible to somehow store a $n$ bit string using only $\mathcal{O}(\log{n})$ space? I am thinking if the string could be stored using a hash function, but I am not sure if it is even possible.
1
vote
0answers
22 views

Configuration of a space bounded turing machine

A configuration of a Turing machine is defined as the following: an ordered triple $(x, q, k) ∈ Σ^* × K × N$, where $x$ denotes the string on the tape, $q$ denotes the machine's current state, and $k$...
1
vote
0answers
32 views

Space usage of recursive functions with no return

Consider an algorithm for reversing a sequence given below: ...
1
vote
0answers
16 views

What is the space-complexity of a boolean first-order query?

I have the intuitition that, if we implement a (space-efficient) boolean first-order query solver, the amount of consumed memory should depend on the data size (i.e., it should not be constant). ...
5
votes
1answer
63 views

Is there a polynomial sized arithmetic formula for iterated matrix multiplication?

I found an article on Catalytic space which describes how additional memory (which must be returned to it's arbitrary, initial state) can be useful for computation. There's also an expository follow ...
1
vote
0answers
53 views

Complexity in time and memory for graph search algorithm

I am working on an assignment where I have to write an algorithm to detect all vertices that lie in a cycle in a graph and then calculate its complexity. I have come up with an algorithm in pseudocode....
2
votes
1answer
42 views

Expressivity of neural networks, how much information can be stored

I want to know whether a given neural network (with a finite number of nodes) is able to store all injective maps f: D -> C, where D has cardinality k and C has cardinality N (so the number of maps ...
1
vote
1answer
101 views

Is in-place run length encoding possible in O(1) space given that the output is shorter than the input?

This is inspired by a problem from here. This is the approximate form of the problem: Given a string like "aaaa777cbb" (10 symbols long), run length encode it in-place to a string like "...
1
vote
0answers
32 views

A genral Turing model with one tape to define sublinear space (L,NL,..)

A genral Turing model with one tape to define sublinear space (L,NL,..) Normally to define sub-linear space complexity we need special Turing models with many tapes, at least two: a read-only tape and ...
2
votes
2answers
71 views

Finding the most frequent element assuming $\Theta(n)$ frequency

We know [Ben-Or 1983] that deciding whether all elements in an array are distinct requires $\Theta(n \log(n))$ time; and this problem reduces to finding the most frequent element, so it takes $\Theta(...

1
2 3 4 5
9