Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
2
votes
0answers
57 views

Is PSPACE vs NEXPTIME known?

I know that P = PSPACE is a famous open problem, and that EXPTIME = NEXPTIME is also unknown. By the time heirarchy theorem we know that NP is a strict subset of NEXPTIME. Is anything known about ...
2
votes
0answers
61 views

What is the computational complexity of the first-order theory of real arithmetic?

Tarski proved that the first-order theory of real-closed fields is decidable. Is the exact computational complexity known? The best upper bound I could find is EXPSPACE [1], where it is also ...
2
votes
0answers
74 views

Why is a pointer constant space?

If a pointer specifies a point in memory, would the amount of space a pointer takes not be dependent on how much memory it could possibly range over? So for example, if we have 4 locations of memory ...
2
votes
0answers
53 views

Proving that the sum of DTIME and DSPACE are not equal

I have an example question from a textbook where it asks to prove that $\Sigma_k DTIME(2^{n^k}) \neq DSPACE(2^n)$. There isn't a solution provided in the textbook. I've been working with a solution ...
2
votes
0answers
265 views

Natural logspace complete problems

After Omer Reingold's famous proof (from 2005?) that SL = L, the distinction between natural L complete problems and natural SL complete problems has been mostly dropped, so that it became difficult ...
2
votes
2answers
115 views

What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)?

What is the space complexity of function $f(x) = \sum_{i=1}^x g(i)$ where g(n) is O(n)? Is it O(n) because the maximum stack size is n, or is it O($n^2$) because there are $n(n+1)/2$ memory ...
2
votes
0answers
146 views

Hamming numbers for $O(N)$ speed and $O(1)$ memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers. Is ...
2
votes
0answers
59 views

Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
2
votes
0answers
730 views

PSPACE completeness, with different kinds of reductions [closed]

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
2
votes
0answers
678 views

Sorting array with constant memory

Given an array of length $n$ we need at least $O(\log n)$ memory to store its length. And we need the same $O(\log n)$ memory to store index. With large $n$, index may not fit in one extra cell. So ...
2
votes
0answers
19 views

Generalized Geography with repetitions [duplicate]

Consider the "Generalized Geography" game: on directed graph G with selected start node, players take turns moving along edges, without ever going back to previously visited nodes. Last player to move ...
2
votes
0answers
319 views

Logarithmic space difference between deterministic and non-deterministic algorithms

I had an interview today, and the interviewer has told me about a theorem (of someone called Hill- or Hell-something) which states that for a non-deterministic algorithm there exists a deterministic ...
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 ...
1
vote
2answers
127 views

Why is the run time of an $f(n)$ space decider bounded by $2^{O(f(n))}$?

In the proof of Savitch's theorem from the 3rd edition of Sipser's Intro to Theory of Computation, Sipser claims that the maximum time that an $ f(n) $ space nondeterministic Turing machine that halts ...
1
vote
2answers
514 views

Is every regular/context free langauge decidable in LogSpace?

I know all the regular languages are decidable but not sure whether it can be done in LogSpace.
1
vote
1answer
341 views

PSpace-completeness under PSpace reductions

A language $L$ is PSpace-complete, if it meets two conditions: It is in PSpace. Every other PSpace-complete language reduces to it in polynomial time. Question: suppose we change the second ...
1
vote
2answers
800 views

Show that NP is not equal to SPACE(n)

I want to show that $\text{NP} \neq \text{SPACE}(n)$ and tried it like this: Let $L$ be in $\text{SPACE}(n)$ so there is a deterministic $k$-tape TM which decides $L$ in polynomial time. Let's ...
1
vote
1answer
180 views

Inclusion of complexity classes (Deterministic Turing Machine)

I can't understand what my professor wrote about these inclusions concerning deterministic classes: $$ DTIME(f) \subseteq DSPACE(f) \subseteq \sum_{c\in\Bbb N}DTIME(2^{c(log+f)}) $$ I understood ...
1
vote
2answers
55 views

STCON in L using matrix multipication algorithm?

I'm trying to understand why the following is incorrect. Given a $STCON$ problem, specifically a graph and nodes $(G, s, t)$, we can assume we are given it's adjacency matrix, $A$. By adding self-...
1
vote
2answers
127 views

Best way we know search for an integer

Basically, you have $n$ integers. The data structure is for your choice, it is ok to do polynomial time preprocessing on them. Then you have multiple questions "Is an integer $k$ in the set?" My ...
1
vote
1answer
79 views

Complexity of recognizing whether two $\omega$-regular expressions represent the same language

If the complexity of recognizing whether two regular expressions represent different languages is EXPSPACE-complete, then what can be said for the complexity of recognizing whether two $\omega$-...
1
vote
1answer
129 views

Prove that 2-Colourability is in L from Undir-Reachability is in L

Let Undir-Reachability be the following problem: given an undirected graph G and two specified vertices s and t in G, is there a path from s to t in G? I need to prove that the 2-Colourability is in ...
1
vote
1answer
264 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
2answers
54 views

What are some decidable problems which cannot be solved in real life(due to time and memory constraints)?

The first line of Sipser book for the Chapter- 'Time complexity', says that: Even when a problem is decidable and thus computationally solvable in principle, it may not be solvable in practice if the ...
1
vote
2answers
105 views

Is $2^n$ steps enough to tell if DTM will run forever?

In the space hierarchy theorem proof for PSPACE from Wikipedia, we reject the input after $2^{|f(x)|}$ steps on the machine $M$, reportedly to avoid infinite running time. My question is: how is it ...
1
vote
1answer
102 views

What does $L$-uniformity mean?

I've understood that $L$-uniformity means that there's a TM that can output the description of $C_n$ in $O(\log n)$ space. Now, that seems odd to me since the description itself (as far as I ...
1
vote
1answer
3k views

How to avoid loops/cycles in iterative deepening with linear space?

Breadth first graph search adds states that have already been visited to an explored set to avoid getting stuck in loops and cycles. This is fine since breadth first search needs exponential space to ...
1
vote
2answers
67 views

Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$

Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a[x] > a[y] + a[z]$. I can think of two solutions: Go over all triplets of indices $x,y,z$ directly. This takes time ...
1
vote
1answer
574 views

Logspace Transducer

I know that a logspace transducer is a deterministic Turing machine that enables us to use log-space complexity. I do not understand though why that is correct. Whatever algorithms can be implemented ...
1
vote
2answers
108 views

Prove that $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete

I need to prove that the following problem $0$-$1$ $\mathsf{ Ineq}$ is $\mathsf{NL}$-complete. Given a finite set of variables $V$, a finite set of inequalities of the form $x \le y$ (where $x, y \in ...
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 ...
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
1answer
35 views

Injectivity verification in o(n) space and O(n) time

The problem I want to solve is this: Given a list $A$ of $n$ elements, I want to verify that they are all distinct. If I were to do this "myself", I would need $O(n)$ space and $O(n\log n)$ time to ...
1
vote
1answer
27 views

$NL^2 = NDSPACE(\log^2n)$ is closed under complement

From Savitch's theorem we have $NL^2 \subseteq L^4$, which is deterministic and thus closed under complement. From Immerman–Szelepcsényi theorem we have $NL = coNL$. Why then $NL^2 = coNL^2$
1
vote
1answer
147 views

Does Multitape reduction to a one tape machine preserve space complexity?

Suppose a Turing machine $M$ has a read-only input-tape and $k$ read-write work-tapes whose non-blank cells are each bounded by $f(|x|)$ where $|x|$ is the length of the input. Is there some constant ...
1
vote
1answer
224 views

Why is DTIME(n) not equal to NP, and consequently, DSPACE(n) not equal to NP?

Intuitively it would seem like these equalities are false since DTIME(n) and DSPACE(N) are in terms of deterministic Turing machines and NP is non-deterministic, but I'm struggling to come up with a ...
1
vote
1answer
28 views

What is the relationship between the complexity class $L^n$ and $NL^m$?

The space hierarchy theorem shows that $$\mathrm{\mathbf{L}}^{1} \subsetneq \mathrm{\mathbf{L}}^{2} \subsetneq \cdots \subsetneq \mathrm{\mathbf{L}}^{m} \subsetneq \cdots \subsetneq \mathrm{\mathbf{...
1
vote
1answer
52 views

If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$?

We know that if $B$ is in $P$ and if $A \leq_p B$ then $A$ is in $P$ too. If $B$ is in $SPACE(n^2)$ and $A \leq_p B$ then so $A$ will be in $SPACE(n^2)$? I think that the answer to this question is ...
1
vote
1answer
506 views

If A is NL-complete then complement of A is also NL-complete?

We know that coNL = NL. But, is this also true? If A is NL-complete then complement of A is also NL-complete? I don't see a reason for that it could be true.
1
vote
1answer
174 views

Any algorithm polynomial time with infinite space?

If I had an arbitrary amount of space at my disposal, couldn't I vectorize/parallelize any program in such a way that it would only need one step? For example, I could let my CPU have an inbuilt look-...
1
vote
2answers
100 views

Find $i$-th number in unsorted sequence in logspace (deterministic turing machine)

There is given input - words is sequence of numbers: $w_i$ is number in sequence, $i$ is position. All of them are in written in binary system. $$w_1\#,...\#w_k\#i$$ Prove that there ...
1
vote
1answer
116 views

Confusing method of proving PSPACE-completness

I don't understand a way of proving PSPACE-completness. The way was used by my lecturer. I can use reduction, however following method confuse me: We consider sequence (of polynomial length) of ...
1
vote
1answer
136 views

Demonstration that EXP is closed under union complementation and concatenation

How can I demonstrate that the EXP class is closed under union, concatenation, and complementation?
1
vote
1answer
868 views

Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
1
vote
1answer
217 views

PSPACE languages reducible to other PSPACE languages in polynomial space

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?
1
vote
1answer
87 views

Space complexity problem, relation between $DSPACE(log^kn)$ and $DSPACE(log^{k+1}n)$

I need help with the following: Let $k\in \mathbb{N}$, define: $L^k=DSPACE(O(log^k(n)))$ $NL^k=NSPACE(O(log^k(n)))$ and: $PolyL=\bigcup_{k=1}^{\infty}L^k$ $PolyNL=\bigcup_{k=1}^{\infty}NL^k$ I need ...
1
vote
1answer
144 views

ALL_{REGEX} in PSPACE algorithm

$ALL_{REGEX}$ is the computational problem of determining for regular expression x if $L(x) = \Sigma^*$. In a proof for $ALL_{REGEX} \in PSPACE$, the following non-deterministic turing machine $M(R)$ ...
1
vote
1answer
2k views

Proving that the language SPACE TMSAT is PSPACE-complete? [closed]

I'm trying to prove that the language SPACE TMSAT (where SPACE TMSAT = {⟨$M$, $w$, $1^n$⟩ : DTM $M$ accepts $w$ in space $n$}) is PSPACE-complete. My solution is as follows: SPACE TMSAT $= \{<M,w,...
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
4
5
6 7 8