Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
1
vote
0answers
17 views

LogSpace reductions vsю PTime reductons for defining PSpace-completeness

Continuing Is every PSPACE-complete problem complete with respect to logspace reductions? : earlier, PSPACE-completeness was defined via logspace reductions (e.g., cf. http://www.cs.cornell.edu/~kozen/...
2
votes
1answer
55 views

Is Space Complexity Always Less Than Or Equal To Time Complexity?

Background I am working on proving a novel problem to be P-Complete, and this requires using a logspace reduction to reduce some known P-Complete problem to the novel problem. Particularly, I am ...
1
vote
1answer
24 views

Why log-space reduction is used for NL-completeness while PSPACE reduction isn't used for PSPACE completeness?

NL-Complete languages are defined by Log-space reduction, while PSPACE complete languages are defined by poly-time many-to-one reduction. According to these posts : Why not polynomial-space ...
5
votes
2answers
1k views

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

I read this problem as a part of my course curriculum, in my professor's notes. I am not able to understand about the standard solution, that if I list all the possible triplets of vertices as 3-...
-1
votes
0answers
22 views

How to calculate the time and space complexity of this scheduling algorithm? [duplicate]

How to time and space complexity of the following algorithm? ...
1
vote
2answers
41 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 ...
0
votes
0answers
35 views

Maximum space consumption of stack and queue for DFS and BFS

I'm trying to determine the maximum memory consumption of the "pending nodes" data structure (stack/queue) for both travelings: BFS and (preorder) DFS. Since BFS and DFS while traveling graphs have ...
1
vote
1answer
32 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 ...
0
votes
1answer
27 views

Can you determinize an NFA in PSPACE?

QUESTION Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$? MORE DETAILS I'm asking this as I want to be able to ...
0
votes
1answer
29 views

TQBF PSPACE-COMPLETE : Why this algorithm is exponential but Savitch's not?

So this is a question pertaining to the proof for $PSPACE-COMPLETE$ (for TQBF for example). The idea is to first prove the $L$ $is$ $PSPACE$(easy part) and next is to prove $PSPACE-COMPLETE$. The ...
0
votes
1answer
47 views

Proving that $NPSPACE\subseteq PSPACE$ using the proof of Savitch's Theorem

We were shown a proof of $NPSPACE\subseteq PSPACE$ in class. In short, the proof says: Let $L\in NPSPACE$. Then there exists a non-deterministic polynomial space bounded Turing machine $M$ that ...
0
votes
0answers
33 views

Logarithmic reduction from Clique to Half-Clique

so the question is in the title basically but I am now studying for a Complexity Theory Exam and encountered this problem in the exercises. I understand how to make a poly-reduction but I am not able ...
1
vote
1answer
81 views

Worst Case Space Complexity of Merge Sort and Bubble Sort

I understand that the worst space complexity of Bubble Sort is constant O(1), since all the space we need is the array where the elements were stored. But why is Merge Sort's worst space complexity O(...
0
votes
0answers
34 views

Is the language $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$ decidable?

I have stumbled upon this language: $L = \{(M,m,n)|\exists x \in \{0, 1\}^n:M$ uses $m$ space on input $x$$\}$. At first, it looked like an undecidable problem, but I have failed to prove it, and now ...
2
votes
0answers
36 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
1answer
128 views

Sorting an array of strings by length in linear complexity

I am trying to find an algorithm to sort an array of strings by length in O(n) time complexity, and O(1) space complexity. The max length of the strings is known. Because of that, I tried using ...
1
vote
2answers
48 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 ...
3
votes
1answer
61 views

Algorithm to compute sum of cost of all path between pair of unique vertices of a tree

Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices. Thus, there are total nC2 or n(n-1)/2 such ...
1
vote
1answer
25 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
60 views

How to prove $L \notin \texttt{DSPACE}(f)$

I want to prove that a language $L$ is not in $\texttt{DSPACE}(f(n))$, the class of languages that a deterministic Turing machine can decide with fixed tape length of $f(n)$ (wiki). That is, I want to ...
1
vote
1answer
18 views

Complexity and hardness of undirected path

Let $PATH = \{(G,s,t) \mid \exists \text{path from}~s\text{ to }t\text{ in }G\}$, where $G$ is a directed graph. We know that $PATH$ is $NL$ complete. I am wondering what the complexity class of $PATH$...
1
vote
0answers
31 views

Space(n) and Space(n^2) implications

I've a problem where I have to prove the following statements: (i) if $SPACE(n) \subseteq P \implies SPACE(n^2) \subseteq P$ (ii) if $P = SPACE(n) \implies SPACE(n) = SPACE(n^2)$ For the Space ...
2
votes
1answer
27 views

NL-Hardness of Target

When revising for an upcoming exam in complexity theory, I came across this problem on the final part of a question, which I was unable to solve: $ TARGET = \{<G, t> : t\ is\ reachable\ from\ ...
1
vote
1answer
327 views

Difference between auxiliary space v/s space complexity

I'm confused between these two terms as for example - the Auxiliary space of merge sort, heapsort and insertion sort is $O(1)$ whereas Space complexity of merge sort, insertion sort, heapsort is $O(n)$...
2
votes
1answer
656 views

Do regular languages belong to Space(1)?

I was wondering, if we take some regular language, will it be in Space(1)? For a regular language X, for instance, we can construct an equivalent NFA that matches strings in the regular language. ...
0
votes
1answer
30 views

Can CNF with an input string be evaluated in logarithmic space?

I have been trying to solve satisfiability of {$<c, w>$ | $c$ is a CNF and $w$ is a binary string which satifies the $c$}. As first looks to me, it is satisiable in linear time ($O(n)$) since ...
0
votes
1answer
29 views

Generalized geography game graph

I'm studying the Sipser textbook for my theory of complexity class. In a part of the book (i.e., Space Complexity chapter), for showing that Generalized Geography game is PSPACE-complete, the author ...
4
votes
1answer
101 views

Merge sort in place

I don't quite understand why in-place sort merge sort isn't preferred over not-in place? Is it because theoretically in place merge sort is better because of its memory complexity tradeoff, but in ...
1
vote
1answer
114 views

How to prove that {<M1, M2> : M1 and M2 are two DFAs and L(M1) $\neq$ L(M2)} is in NL?

My idea is to find a turing machine which recognizes this language in $\log N$ space, could anyone give me some clue on how to find such turing machine?
0
votes
1answer
30 views

Constructing a DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$ with a kind of log-space TM

Suppose that $A$ and $B$ are DFAs. We know that there is some DFA $M$ such that $L(M) = L(A) \bigtriangleup L(B)$, the symmetric difference. Also, we can construct this $M$ by some Turing machine $N$. ...
3
votes
1answer
73 views

How to prove SPACE-TMSAT is PSPACE-hard?

I understand that the language: $\operatorname{SPACE-TMSAT} = \{⟨M, w, 1^n⟩ : \text{DTM $M$ accepts $w$ in space $n$}\}$ is in PSPACE since it doesn't use more than $n$ space. But to prove that it ...
4
votes
1answer
136 views

Non-existence of PSPACE-hard unary language

I'm trying to prove that unless $\mathsf{P}=\mathsf{PSPACE}$, there is no unary language which is $\mathsf{PSPACE}$-hard. Assuming there is an unary language $A$ which is $\mathsf{PSPACE}$-hard, it ...
0
votes
0answers
20 views

Analysis Or Review Of Article “Table Design In Dynamic Programming”

I was wondering if anyone could point to some sort of review to this paper "Table Design In Dynamic Programming" by Peter Steffen and Robert Giegerich? https://dl.acm.org/citation.cfm?id=1182768 Has ...
1
vote
0answers
30 views

Time and space complexity of a recursive problem (code included)

I am having trouble finding out the time and space complexity for this recursive solution. I have to create a list of words in order of word length. Each word, must be one character insertion off from ...
1
vote
1answer
287 views

Is Breadth First Search Space Complexity on a Grid different?

Is the Space Complexity O(number_rows + number_cols) for Breadth First Search on a Grid. This is an attempt to show my reasoning: For example, the flood fill question is described here: https://www....
0
votes
1answer
55 views

How do I prove that SPACE($n^{555}$) $\neq$ NP?

I thought about finding a language with a polynomial verificator "larger" than $n^{555}$, but then I realized it would not imply the space needed for computation is the size of the verificator.
0
votes
0answers
43 views

Relationship between SPACE(t(n)) and DTIME(t(n))

I'm new to complexity theory and am analyzing inclusions between complexity classes. Suppose we are given the following seven complexity classes $DTIME(n)$ $DTIME(n^2)$ $DTIME(2^n)$ $DTIME(2^{2^n})$ $...
1
vote
0answers
35 views

Is there a difference in space complexity between inner product of matrices to multiple of inner products where each containing one matrix at a time?

The book I am reading is suggesting the following: Suppose I have two vectors $v, w$ and $P(n)$ matrices $U_1, U_2, \ldots, U_{P(n)}$. Then performing an inner product of $v$ with $U_1U_2\ldots U_{P(...
4
votes
2answers
104 views

Proof of Space Hierarchy Theorem incompatible with Linear Speed Up Theorem for time

In this proof of the Space Hierarchy Theorem the following langugae is defined $$ L = \{ (\langle M \rangle, 10^k) : M \mbox{ does not accept } (\langle M \rangle, 10^k) \mbox{ using space } \le f(|\...
4
votes
1answer
303 views

What's after EXPSPACE?

As far as I'm aware, EXPSPACE is the most inclusive computational complexity class. I was wondering if/how people conceptualize supersets of EXPSPACE. Thinking about this question, I came up with a ...
0
votes
1answer
62 views

What is space complexity of shrinking one array to increase another?

Say I have an array and I want to add those values to something else. What is the space complexity if I incrementally take one of those values off the first list and add it to the second? For example, ...
0
votes
0answers
67 views

Time complexity of well know constraint satisfaction problem algorithms with heuristics

I have know that complexity of csp algorithms as follow: Backtracking algorithm for constraint processing space:O(n) ,Time :O(expn) Backjumping algorithm for constraint satisfaction problem ...
0
votes
0answers
39 views

Is there a known lower bound on the time/space complexity of DFA minimization?

I've read the Wikipedia page on the topic, but there's no mention of a lower bound on the time complexity, and there's no mention of space complexity at all.
1
vote
1answer
221 views

Max number of configurations of a Turing Machine

I was wondering about a result in the Sipser book which states that any $f(n)$ space bounded Turing machine also runs in time $2^{O(f(n))}$. Is this because a configuration consists of a state, a ...
5
votes
2answers
514 views

Logic behind O(n) solution for 'Maximum length sub-array having given sum'

I am unable to understand the logic behind O(n) solution of this classical problem- Maximum length sub-array having given sum (...
2
votes
1answer
310 views

Time complexity to find Median of Medians

I recently wrote my Grad school Admission test few days back and the following question appeared in the test. There are 'n' unsorted Arrays : A1, A2, ...., An. Assume that 'n' is odd. Each of A1, A2, ....
2
votes
0answers
36 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 ...
1
vote
1answer
28 views

Better implementation to find the root of an element in QuickUnion implementation of UnionFind problem

I wanted to know which implementation is better to find the root of the element in the Quick Union implementation of the UnionFind problem. The professor has used a while loop to find the root of the ...
0
votes
0answers
43 views

Space complexity for accepting word decision problem of DFAs

It is well known that the the decision problem $w \in \mathcal{L}(M)$ for a DFA $M=(Q,\Sigma, \delta, q_0,F)$ is in $\mathcal{O}(|w|)$. To proof this we assume that the successor state computation can ...
6
votes
2answers
204 views

Return copy of array, each element product of all others, constant additional space, no division

Question: I am trying to solve question 6.10.1 from Elements of Programming Interviews. The task is as follows: Given an array $<a_1, \ldots, a_n>$ of fixed-...