Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

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

EXPTIME $\neq$ EXPSPACE consequences?

We know that $EXPTIME ⊆ NEXPTIME ⊆ EXPSPACE$, where $EXPSPACE = DSPACE(2^{poly(n)})$. Question: Is known any consequences of $EXPTIME \neq EXPSPACE$? (nothing in complexity zoo or wikipedia)
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 ...
3
votes
1answer
63 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$ ...
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 ...
3
votes
1answer
166 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 ...
2
votes
1answer
144 views

Space complexity of boolean circuit evaluation

I am given a boolean circuit of depth $D \ge \log n$ where $n$ is the input size. Given an input, I need to find an algorithm that evaluates the circuit in space $O(D)$. Now, assuming the fan in of ...
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 ...
0
votes
0answers
120 views

show doubly connected graph is NL complete

The question:A directed graph is doubly connected if every two vertices are connected by a directed path in each direction. Let DCG = {| G is a doubly connected graph} Prove that DCG is NL-complete. (...
0
votes
1answer
102 views

Space complexity for connectivity problem with given graph diameter

Given $(G,D,d)$, a graph, the graph diameter and the maximum outdegree of the graph. Verify that $G$ is strongly connected in $O(D\log d + \log n)$ space complexity. I thought about using the $STCON$ ...
0
votes
0answers
102 views

Generalized Geography problem time and space complexity

We all know the algorithm that solves the Generalized Geography problem using polynomial space (it's described on wiki). My question is: what is the time complexity of this algorithm? I'd like a more ...
-2
votes
5answers
548 views

Algorithm to generate non-repeating random numbers of O(1) memory?

Is it possible to create $O(1)$ memory consuming algorithm, which is generating non-repeating pseudo random numbers? I can remember numbers in the hash set and it will be $O(1)$ time, but the set ...
2
votes
1answer
527 views

How to prove that $n\log n$ is space constructible?

I'm trying to prove that $n\log n$ is space constructible. I've already managed to prove that $\log n$ is space constructible, but I cannot figure out how to prove the same about $n$. I assume, that ...
0
votes
0answers
66 views

Row-Column agnostic Matrix datastructure

Due to the linear nature of computer memory, row-major and column-major matrices have different performance for row- vs. column access. The obvious solution would be to keep two copies of the same ...
1
vote
1answer
498 views

How to show MULT={a#b#c| a,b,c binary natural numbers and a ✕ b = c} is in Log Space?

Let MULT$=\{a\#b\#c| a,b,c \text{ binary natural numbers and } a\times b=c\}$ Prove that MULT $\in L$ How do I show that this language, MULT, is computable in Logarithmic space? Let us assume a#b#c ...
1
vote
0answers
25 views

United space-time complexity of finite strings

Let's consider bit string as a program for some computational model. If after $k$ steps program represented by number $n$ halts and outputs bit string $s$, then complexity of s is (n+1)*k. For example ...
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 ...
4
votes
1answer
574 views

Median-of-medians in O(log n) memory

Is there a way to use median-of-medians to find a median in, simultaneously, ​ ​O(log n) ​ ​memory and O(n) comparisons? The user orlp on this site seems to claim that there is. Getting ​ ​O(log n) ...
1
vote
1answer
347 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 ...
3
votes
1answer
2k views

Prerequisites of computational complexity theory

what's the prerequisite topics needed for understanding computational complexity theory and analysis of algorithm ...including big-O and Big-theta notations and these staff. I want a mathematical ...
5
votes
1answer
186 views

Space-unconstructable function in the proof of Savitch's theorem

I'm learning about the Savitch's theorem, and while the construction proof is straightforward, I still don't understand one part about it. The proof I'm talking about is the same as is currently on ...
3
votes
1answer
69 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/...
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 ...
3
votes
1answer
804 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 ...
1
vote
0answers
454 views

Is PSPACE closed under the following forall-there-exists construction?

Suppose I have a language $L$ (over alphabet $\Sigma$), such that $$ w \in L \iff (\forall x \in \Sigma^*) (\exists y \in \Sigma^*) P(x,y,w). $$ and I can give a turing machine that decides $P(x,y,w)$ ...
9
votes
1answer
3k views

Does space complexity analysis usually include output space?

Since most examples of complexity analysis I've seen involve functions that return either nothing (e.g. in-place sort) or a single value (e.g. computation, lookup), I haven't been able to figure this ...
0
votes
0answers
154 views

Proving SAT is in L

How to prove that SAT is in L if and only if NP=L? I know that reducing SAT in cook-levin theorem is computable in deterministic linear space . How to do it in log space? Any reference will also help.
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
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 ...
3
votes
2answers
1k views

How to compare algorithms having the same complexity

I am new to programming and want to learn how to compare algorithms having the same complexity and pick the best one. Certain problems can be sloved using several algorithms which have the same ...
0
votes
0answers
143 views

Alternating Turing Machine: Why one cannot generalize the proof of AL = P?

In their paper "Alternation" Chandra et al. show how an Alternating Turing Machine can simulate a Deterministic Turing Machine with time-complexity $t(n)$ using only $\log(t(n))$ space what implies $P ...
5
votes
3answers
1k views

Which class of languages is accepted by PDA when we restrict the stack to logarithmic size?

Let $\mathrm{LOG}_{\mathrm{CF}}$ be the class of all languages recognized by a Pushdown-automaton that uses $\leq \log n$ cells of its stack for each input of length $n$. Obviously, this class is a ...
6
votes
1answer
276 views

Is there a polynomial time algorithm to determine whether an 'up down' language is 'emptible'?

Definitions: An up down language is a language whose alphabet is a set of pairs, but not characters, of two characters, where the one character in the pair is the opposite of the other character in ...
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 ...
2
votes
1answer
50 views

Polynomially many times launch $NL$ machine - is it in $NL$? On example of ACYCLIC

Lets consider $$ACYCLIC = \{\langle G \rangle | G \text{ is acyclic}\}$$ We are going to prove that $ACYCLIC\in NL$. I know that the easiest approach for this task is to use the fact that $coNL=NL$. ...
1
vote
1answer
200 views

Definition of space complexity when algorithm cycles.

I'm reading side by side my class notes and Papadimitrious' Computational Complexity book. At this point they are talking about space complexity. They give rules for computing space employed in an ...
1
vote
1answer
507 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.
0
votes
2answers
2k views

If problem is coNL-complete, is it NL-complete

We know from Immerman-Szelepcsényi theorem that $coNL=NL$. But, what about: If problem is $coNL\text{-}complete$, is it $NL\text{-}complete$? And why?
0
votes
1answer
52 views

Show that checking if there exists word not containg patterns from list is in $PSPACE$

There are given: alphabet $Σ$ with some symbols $a,b$. list of forbidden patterns Result: Is there exists word of form $a\Sigma^*b$ such that it doesn't contains (as subword) any of word from list ...
2
votes
1answer
747 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 ...
0
votes
0answers
69 views

P-complete problem due to logspace reductions. What does it mean?

Prove that problem $A$ is complete in $P$ due to reductions computed in logarythmic space How to understand this statement ? What should be shown ? For me: 1. $A$ is in $P$. 2. Each problem in $...
1
vote
1answer
175 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
1answer
457 views

Convert conjunctive normal form to equivalent boolean formula with only NAND gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NAND gates with ...
0
votes
0answers
112 views

Convert conjunctive normal form to equivalent boolean formula with only NOR gates

Let $\varphi$ be a boolean formula in 3-CNF form (conjunctive normal form with three literals at most per clause). I want to convert it to an equivalent boolean formula that uses only NOR gates with ...
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 ...
2
votes
1answer
60 views

What is the complexity to show this theorem?

Given a sum of regular expressions, where each regular expression in the sum is n-1 concatenations of 0, 1 and (0+1). There is need to show that the sum of all regular expressions is either equal to ...
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 ...
3
votes
1answer
234 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 ...
1
vote
1answer
191 views

Show that problem is PSPACE-complete - path in directed graph

I have a following problem: Given $n$ and graph of size $2^n$, and circuit with $2n$ input gates. Directed edge between $k$ and $l$ exists iff only and only we encode $k$ and $l$ as bits and launch ...
0
votes
1answer
481 views

What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets?

What is the complexity of the problem of computing the cardinality of the union of many (finite) and small sets? What is both the time and space complexity of the naive algorithm that does this ...
5
votes
1answer
737 views

Are there strongly-polynomial algorithms that take more than polynomial time?

In [1] strongly-polynomial is defined as either: The algorithm runs in strongly polynomial time if the algorithm is a polynmomial space algorithm and performs a number of elementary arithmetic ...

1 2 3
4
5
8