Questions tagged [space-complexity]

Asymptotic analyses of the space needed to run algorithms.

Filter by
Sorted by
Tagged with
4
votes
1answer
167 views

$UCYCLE$ is in $L$

I'm trying to understand the log-space algorithm for $$UCYCLE = \{ \langle G \rangle \ | \text{ $G$ is an undirected graph containing a cycle} \}$$ The basic idea is traversing from every $v\in V$, ...
1
vote
1answer
39 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
43 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
396 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
765 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
51 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) ...
2
votes
1answer
454 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
36 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
136 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
132 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
163 views

Solving $UCYCLE$ in logspace - two possible approaches ? Why can't we one of them use to solve connectivity?

$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$ There are two possible approaches to this exercise: Solving cycle in undirected graph in log ...
0
votes
0answers
83 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 ...
0
votes
1answer
292 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 ...
1
vote
2answers
90 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 ...
9
votes
4answers
334 views

A language in NSPACE(O(n)) and very likely not in DSPACE(O(n))

Actually I found that the set of context-sensitive Languages, $\mathbf{CSL}$ ($\mathbf{=NSPACE(O(n)) = LBA}$ accepted languages) are not so widely discussed as $\mathbf{REG}$ (regular languages) or $\...
2
votes
1answer
55 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
81 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
154 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
303 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 ...
0
votes
0answers
89 views

Is the algorithm to solve 4SAT correct and what it's both time and space complexity?

The algorithm works as follows: For each clause, the algorithm turns the middle disjunction into conjunction, i.e. if an arbitrary clause is of the form: (l1 ∨ l2) ∨ (l3 ∨ l4) Then after ...
3
votes
1answer
188 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
83 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 ...
-1
votes
1answer
162 views

What is the time and space complexity of the algorithm to either prove or refute that given expression is equals to (A+B)^n for any natural number n [closed]

Note that this is not duplicate of my previous question: how to simplify algebraic expressions, though it is similar, but still this is different, this is not the same. I need an algorithm that ...
1
vote
1answer
301 views

Complexity of simplifying two-variable algebraic expression

Given algebraic expression of two variables x and y, I want to simplify this algebraic expression until it cannot be simplified anymore. What algorithm can I use for this? For instance: x+x+y+y = 2&...
5
votes
1answer
429 views

Why is CVAL a P-Complete problem?

We've learned in class that CVAL is P-complete. CVAL is the language of all $\langle C,x\rangle$ where $C$ is a formula (a circuit which outputs $0$ or $1$) and $x$ is some input for $C$ such that $C(...
0
votes
1answer
69 views

How large would a database containing perfect knowledge of chess be?

Assuming that a database entry schema contains two 64-bit hash IDs generated via the algorithm explained here, in the section "Generating Hash Keys for Chess Boards", and simply a score that's a 32-...
0
votes
0answers
60 views

Showing if $A\in DSPACE(n^c) \text{ or } DTIME(n^c)$ then $EXP^A \neq EXP$ and $EXP^A= EXP$

If a language $A\in DSPACE(n^c)$, then $EXP^A\neq EXP$ If a language $A\in DTIME(n^c)$, then $EXP^A= EXP$ What I tried: Since it's impossible to show that $EXP \subseteq EXP^A$ because: We ...
2
votes
1answer
149 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 ...
1
vote
1answer
89 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?
6
votes
1answer
260 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
595 views

Space and time complexity of balanced parentheses enumeration algorithm

Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with prefix = $\epsilon$ (the empty string): A(prefix): If prefix ...
3
votes
1answer
290 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:...
13
votes
7answers
4k views

How to check if two strings are permutations of each other using O(1) additional space?

Given two strings how can you check if they are a permutation of each other using O(1) space? Modifying the strings is not allowed in any way. Note: O(1) space in relation to both the string length ...
2
votes
1answer
311 views

Space requirement of a universal Turing machine

Given a representation $g$ (e.g. the Gödel number) of a Turing machine $B$, a universal Turing machine $A$ can simulate $B$. If $B$ is restricted to using at most $n$ memory cells of its tape and the ...
3
votes
2answers
151 views

Which graph algorithm should I use?

I need to find the shortest path in a Directed Unweighted Cyclic graph. And it has to be optimal (find a path if exists one) and also optimal in terms of space and time complexity, being time ...
2
votes
1answer
217 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 ...
5
votes
1answer
138 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 ...
5
votes
2answers
408 views

PSPACE-complete problems can't be in NL using the space hierarchy theorem?

I want to prove that no PSPACE-complete problem is in NL using the space hierarchy theorem. What I want to say is this : From the time hierarchy theorem I know that for every $t(n)$ there exists a ...
2
votes
1answer
443 views

non deterministic space hierarchy

I want to prove the non deterministic space hierarchy theorem. Let $f(n),g(n)\geq\log n$ be space constructible functions such that $f(n)=o(g(n))$, Prove: $$NSPACE(f(n))\subsetneq NSPACE(g(n))$$ I ...
1
vote
1answer
93 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 ...
0
votes
2answers
102 views

Reachibility between first and last layer in grid graph in logspace

I am trying to prove that there exists logspace deterministic Turing machine that check if exists path between first row and last row in grid graph. Grid graph is matrix of $0s$ and $1s$, the ...
3
votes
1answer
239 views

What if there is a polynomial-time algorithm to minimize NFA?

Knowing that NFA-minimization has been proven to be P-SPACE complete, what if there is a polynomial-time algorithm to minimize NFA? Does that imply that P = PSPACE?
0
votes
0answers
59 views

Is there a fundamental concept underlying trade-offs in CS and are they unavoidable?

There are many examples of trade-offs in computer science. The space-time trade-off is a well-known one. Often an increase in memory use can lead to faster execution time, and vice-versa. Caching ...
1
vote
0answers
89 views

Complexity of emptiness checking for visibly pushdown automata?

Visibly pushdown automata [1] are pushdown automata in which input symbol determines whether push or pop operation happens in the stack. Does anyone aware of tight lower bound for their emptiness ...
0
votes
1answer
210 views

Spacetime Tradeoff

I understand that many algorithms have space/time tradeoffs-that is, to run faster, you can do things like caching data, which reduces time taken in exchange for space consumed. Given conservation of ...
1
vote
0answers
428 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)$ ...
0
votes
1answer
2k 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 ...
5
votes
1answer
442 views

Proving that $\mathrm{SPACE}(o(\log\log n)) = \mathrm{SPACE}(O(1))$?

It is known that $\mathrm{SPACE}(o(\log \log n)) = \mathrm{SPACE}(O(1))$ (see e.g. these lecture notes by Christian Scheideler). One inclusion is trivial, so I'm trying to show that $\mathrm{SPACE}(o(...
2
votes
2answers
343 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$. ...
1
vote
0answers
180 views

Misunderstanding the Baker-Gill-Solovay oracle and obtaining $LOGSPACE^A=PSPACE^A$

Baker, Gill and Solovay [1] gave an oracle $A$ relative to which $P^A=PSPACE^A$. The oracle is the very simple $PSPACE^A$-Complete language $$A = \{\langle M, x, 1^n \rangle | M^A \text{ accepts } x \...