Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
3
votes
1answer
749 views

Equality of NSpace and coNSpace classes

I'm trying to decide which of the following statements are true: $\mathsf{NSpace}(\log \log n) = \mathsf{coNSpace}(\log \log n )$ $\mathsf{NSpace}(\lg^2n) = \mathsf{coNSpace}(\lg^2n)$ $\mathsf{NSpace}...
3
votes
2answers
10k views

Time and space complexity of Radix sort

I had previously asked a question on space complexity of radix sort here. I have also read this question. However, I still get confused about it which means that the concept is not clear. I have the ...
3
votes
1answer
107 views

Is $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$?

We know that $\mathsf{DSPACE}(\log\log n) = \mathsf{DSPACE}(1)$ according to this proof. Can we claim that $\mathsf{DSPACE}(n)=\mathsf{DSPACE}(n/\log\log n)$ or something like $\mathsf{DSPACE}(n^3)=\...
3
votes
1answer
295 views

Does the space complexity of a recursive algorithm depend on the total no of recursive calls?

I am confused whether space complexity of a recursive algorithm depends on the total number of recursive calls or not. Say I have an algorithm which has exponential function calls, but stack size is ...
3
votes
1answer
86 views

The read tape in the definition of L and NL (logarithmic space) (DLOGSPACE, NLOGSPACE) (sublinear space)

By the definition of L=DLOGSPACE or of NL=NLOGSPACE (or any sublinear space class) there is an extra tape (for the Turing machine): the input tape, which is only for reading - but for arbitrary ...
3
votes
1answer
310 views

Understanding of SPACE in non deterministic Turing Machines

Let's consider the following situation. We have a finitie alphabet $A$. Let $A = \{a_1, .., a_k\}$ We consider words over $A$ of length exactly $n$. I am trying to solve some problem and I am going to:...
3
votes
1answer
147 views

More details on a language decided in $\Theta(\log \log n)$ space

In Language with $\log \log n$ space complexity?, the following non-regular language is described: $$L = \{b(0) \# b(1) \# \dots \# b(2^k-1) \mid k\in \mathbb{N}\}$$ where $b(i)$ is the $k$-bit ...
3
votes
1answer
42 views

The class of languages that can be certified in a small amount of space

NP can be characterized in two different ways, one of them is that it's the class of languages that can be certified by a witness in a polynomial time. I wonder, if we consider the same notion but ...
3
votes
1answer
117 views

complexity of modal logic axioms

I am writing a paper in which I want to include complexity results for different modal logics and possibly add a reference to a specific paper. At the moment I have the following: K- no restrictions ...
3
votes
1answer
851 views

Acyclic Graph in NL

From the book The Nature of Computation by Moore and Mertens, exercise 8.9: Consider the problem ACYCLIC GRAPH of telling whether a directed graph is acyclic. Show that the problem is in NL, and ...
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 ...
3
votes
1answer
145 views

Does the circuit value problem require only log space in alternating Turing machines

Why does the circuit value problem run in log space on an alternating Turing machine? It is claimed to be so in my university's lecture notes. Also, it is claimed that monotone circuit value problem ...
3
votes
1answer
193 views

Question about space complexity

I'm trying to represent a directed acyclic graph using a structure similar to an adjacency list. The difference is, for a given vertex v, I need to know precisely which nodes are inwardly adjacent to ...
3
votes
1answer
442 views

Membership problem for context sensitive languages PSPACE-complete

I have read that the membership problem for CSL is PSPACE-complete but I couldn't find the proof anywhere. So I tried it myself. Let's mark the membership problem for CSL as MEM. First I have to ...
3
votes
1answer
2k views

Show Recognizing two Regular Expressions as equal is in PSPACE

If I have $EQ_{REX} = \{\langle R,S \rangle|\text{ $R$ and $S$ are equivalent regular expressions}\}$, how do I show that $EQ_{REX}\in PSPACE$ ? What I know so far is that there are decidable ...
3
votes
1answer
546 views

What is a good example of an NL-complete context free language?

Setting Exactly as the title stated: Give an example of an $\mathsf{NL}$-complete context free language. $\newcommand{\angle}[1]{\langle #1 \rangle}$ Current Solution Recall in the past we ...
3
votes
1answer
310 views

Log-Space Reduction $CO-2Col \le_L USTCON$

I want to show that $CO-2Col \le_L USTCON$ (Log-Space reduction) $USTCON$ The $s-t$ connectivity problem for undirected graphs is called $USTCON$. [Input]: An undirected graph $G=(V,E)$, $s,...
3
votes
1answer
2k views

Prove the following problem is NL-complete

Suppose $$A = \left\{\langle G, d, s, t\rangle \;\Bigg|\; \begin{array}{l} \text{\(G\) undirected}, \\ \text{\(s\) and \(t\) are nodes in \(G\)}, \\ \text{there is a path of length \(d\) from \(...
3
votes
1answer
81 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 ...
3
votes
1answer
56 views

Graphs in space efficient representation

Let $G$ be a graph such that $V$ denotes a vertex set and $E$ is an edge set of the graph $G$. Let us consider that for the input graph $G$ it is the case that $|E| \le O(|V| \log |V|)$. Given a graph ...
3
votes
1answer
54 views

Connecting strings in a graph is a PSPACE problem

We define the following problem as: Let $M$ be a TM with alphabet $\Gamma$, with $\{a,b,$ #$\} \subset \Gamma$. We define, for every natural number $n$ the graph $G_{M,n}$ by: $V_{M,n} = \{a,b\}^n$,...
3
votes
1answer
679 views

Fast, stable, almost in-place radix and merge sorts

I've developed LSD radix sort algorithm that is stable, about as fast as the classic LSD radix sort, require only $O(\sqrt{RN})$ extra space when we sort into R buckets. The same technique also ...
3
votes
1answer
59 views

Limited oracle TM

Let $M$ be a Turing machine with oracle to $B$ that can decide $B$ in polynomial time. In the general case it means nothing, since we can just pass the input as a query to the oracle of $B$ and accept/...
3
votes
1answer
60 views

Problem that is only solvable in a given space

I was wondering if a computational problem exists with the following properties: It should be solvable only having $K$ bytes of memory, or solvable with $K' < K$ bytes of memory only in ...
3
votes
1answer
65 views

The complexity of BDD Synchronous Composition

As shown in Byrant's original paper, the time complexity of (single-variable) composition algorithm is cubic, and it is a tight upper bound. My question is about synchronous composition, written as $$...
3
votes
1answer
271 views

why is every self-reducible language in pspace

I understand that every self reducible language recursively queries its oracle with strings of length less than the input size. But how does that show that every such language can be solved in ...
3
votes
1answer
372 views

Showing that the language of graphs and nodes on an odd cycle is in NL

Let L be the language containing all the pairs (G,v) where G is a directed graph and v is a vertex in G such that G contains a cycle that contains v and the number of different vertices that appear in ...
3
votes
1answer
205 views

Polynomial space complexity with exponential size witnesses

Define the complexity class $C$ to be the class of all languages that can be verified by a TM that has: Input tape: Read only, move in both directions. Witness tape: Read only, move only in one ...
3
votes
0answers
49 views

LogSpace reductions vs. PTime reductons for defining PSpace-completeness [closed]

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
2answers
521 views

Counting with constant space bounded TMs

The problem, coming from an interview question, is: You have a stream of incoming numbers in range 0 to 60000 and you have a function which will take a number from that range and return the ...
2
votes
1answer
172 views

Is FACTORIZATION or PRIMES known to be in LOGSPACE

Are the integer factorization and PRIMES known to be in LOGSPACE? Recently, it has been shown by researchers that PRIMES is in P. But this does not say anything about LOGSPACE since it is not known ...
2
votes
1answer
875 views

How hard are PSPACE-complete problems?

There are already good answers from several perspectives regarding the "hardness" of $PSPACE$-complete problems, such as this: What is practical difference between NP and PSPACE-complete? But what ...
2
votes
1answer
155 views

Is $DSPACE(f) \subseteq DTIME(f)$ always?

Is $DSPACE(f) \subseteq DTIME(f)$ always? For example, if we have a language $A\in DSPACE(log^2(n))$ can we say that $A\in P$ (and subsequently in NP and coNP) since $DSPACE(log^2(n))\subseteq ...
2
votes
2answers
387 views

Why L is defined as L = SPACE$( \log n)$ instead of L = SPACE$(\log^2 n)$ or L = SPACE$(\sqrt n)$?

$L$ is the class of languages that are decideable in logarithmic space on a deterministic Turing machine. In other words, L = SPACE$( \log n)$ But why $\log n$, instead of $\log^2 n$ or $\sqrt n$. ...
2
votes
1answer
185 views

Understanding why ALL_nfa is in co-nspace

I'm trying to understand Sipser's example showing that $ALL_{nfa} \in Co-NSPACE(n)$, where $$ALL_{nfa} = \{ <A> | A \text{ is an NFA such that } L(A) = \Sigma^*\}.$$ The algorithm can be seen ...
2
votes
1answer
10k views
2
votes
1answer
57 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 ...
2
votes
1answer
657 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. ...
2
votes
1answer
220 views

Is Not-STCON is NL-Complete?

$STCON=\text{{(G,s,t)|G is a directed graph with a path from s to t}}$ $Co-STCON=\text{{(G,s,t)|G is a directed graph without a path from s to t}}$ I've tried the following proof: Let $S\in NL$, and ...
2
votes
3answers
3k views

What happened if we implement quicksort without tail recursion?

On Wikipedia, it said that The in-place version of quicksort has a space complexity of $\mathcal{O}(\log n)$, even in the worst case, when it is carefully implemented using the following strategies:...
2
votes
1answer
45 views

In certificate view of NL can we force the guesses to be in some format like $a^n b^n c^n d^n$?

In certificate view of NL the size of our guess can be polynomial.Can this guesses be like $a^n b^n c^n d^n$. Can we force the guesses to be in some format? I think it(the format) can be in regex ...
2
votes
1answer
47 views

Is it known that $AC^1 \subseteq L$?

A good exercise is to show $NC^1 \subseteq L$. (According to the complexity zoo page this was first shown by Borodin, 1977.) Although the details must be checked, the proof is simple: take the $NC^1$ ...
2
votes
1answer
484 views

Prove that $L$ is closed under Kleene star iff $L=NL$

Prove that $L$ is closed under Kleene star iff $L=NL$ Hi, I am trying to solve this exercise, but it is quiet difficult. Of course first part is very easy: Let assume that $L=NL$. Lets consider ...
2
votes
1answer
227 views

Does graph connectivity being NP-complete imply NL=P?

I asked this question on cstheory.se before, where someone pointed out that it is equivalent to asking whether P=NP implies NL=P (thus I edited the question accordingly). However, my supervisor ...
2
votes
1answer
368 views

Prove the following language is in L (LogSpace)

I'm trying to prove the following language is in $L$ (decided by a TM in $O(\log n)$ space): $$A = \{ (C,x) \mid C(x)=1\text{ and $C$ is a Boolean formula with depth }\log(n)\}\,,$$ where $n = |(C,x)...
2
votes
1answer
45 views

On graph isomorphism over exponential word sizes

Is it known Graph isomorphism can be done in poly time if we allow exponential word sizes? (Shamir's poly time Integer Factoring algorithm is over exponential word sizes).
2
votes
1answer
121 views

Examples of languages not decidable by a TM using certain upper bounds on space/time

I'm learning about time and space complexity involving Turing Machines at the moment, and would really like some concrete examples of specific languages that belong (or don't belong) to certain ...
2
votes
1answer
468 views

Why is it necessary to use binary numbers in logspace?

I have noticed that a lot of problems that are in L and NL use binary numbers. I don't understand why this is the case. Does a TM use less space by storing a binary number, than a "normal" one. In my ...
2
votes
1answer
312 views

Generalized Geography with repetitions

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 ...
2
votes
1answer
944 views

How to Study Space Complexity

I am working through Sipser, and I am trying to understand some of the algorithms described in Space Complexity, but I am having a hard time understanding the presentation of the material (especially ...