Asymptotic analyses of the space needed to run algorithms.

learn more… | top users | synonyms

1
vote
1answer
24 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 ...
1
vote
0answers
28 views

Parallel time is sequential space

Studying for my qualifying exam, have a past exam here, which has the following question, verbatim: Give a proof of the Folklore statement: "sequential space is parallel time." In other words, ...
-1
votes
0answers
10 views

PSPACE subset of EXPTIME [duplicate]

In computational complexity theory, PSPACE is the set of all decision problems that can be solved by a Turing machine using a polynomial amount of space. In computational complexity theory, the ...
2
votes
1answer
22 views

Looking for an example of proving space upper bounds for computing functions on a DTM

Like think of the function $f\colon \{ 0,1\}^* \rightarrow \{0,1\}^*$ which maps a binary string string $x$ to say a string of $0$s of length $\vert x \vert ^2$ whre $\vert x \vert$ is the length of ...
0
votes
1answer
27 views

Memory Requirement for a Computable Problem

I was thinking whether it is true that every computational problem intrinsically has a minimum ammount of memory required for any algorithm that computes it. But then i was confused to what "memory ...
4
votes
2answers
176 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 ...
1
vote
1answer
35 views

IS and matching

I have 2 different but similar problems, one belongs to NP and one to L and I don't understand why. First problem: Input: an undirected graph G with n^2 vertices. Question: Is there exist in G a ...
1
vote
0answers
22 views

Examples of real world graphs that are too big for a single commodity-type machine

I've been reading on distributed systems for processing on large graphs. The most prominent examples include Pregel (developed by Google) and Apache Giraph. Most of these systems argue their existence ...
1
vote
1answer
20 views

Space penalties for the simulation of a non-deterministic Turing machine by a single-tape deterministic Turing machine

If I have some non-deterministic Turing machine $NDTM$ running some process $Q$ and I wish to simulate the same process $Q$ with a deterministic single-tape Turing machine $DTM$, there will of course ...
1
vote
3answers
360 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 ...
5
votes
1answer
48 views

Which CNF boolean formulas blow up exponentially at conversion to DNF?

If I'm correct, some boolean formulas in CNF require exponential size when being converted to an equivalent DNF version (and vice versa). But what is an example of such a formula (and is there a ...
3
votes
2answers
30 views

Function that is not Space Constructible

I'm reading Sipser's Introduction to the Theory of Computation, and I'm reading about space-constructible functions. He gives the following definition: A function $f: \mathbb{N} \to \mathbb{N}$ is ...
1
vote
0answers
61 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 ...
4
votes
0answers
55 views

Space complexity of statistic functions

When computing statistics on a list of data it occurred to me that most of the standard statistic functions, such as mean, min, max can be computed in O(N) time with O(1) space. They can also be ...
0
votes
1answer
41 views

Decide $\{a^nb^n\mid n>0\}$ in log space

Given $S = \{a^n b^n \mid n > 0\}$, show $S$ is deterministically decidable in log space. Hint: to count up to $n$ you need $\log n$ bits. This comes from some lecture notes at ...
2
votes
1answer
123 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 ...
1
vote
1answer
89 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 ...
2
votes
0answers
232 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 ...
4
votes
4answers
535 views

How can an algorithm have exponential space complexity but polynomial time complexity?

For enumerating the minimal feedback vertex sets of a graph Schwikowski and Speckenmeyer show an algorithm "GENERATE-MFVS" in their publication "On enumerating all minimal solutions of feedback ...
1
vote
1answer
53 views

How to prove strict space lower bounds using crossing sequences in Turing machines?

I understand the notion of crossing sequences when talking about time, however how are they used to actually prove strict lower bounds for some decision/search problems? For example, suppose that you ...
10
votes
1answer
597 views

What does sublinear space mean for Turing machines?

The problem of deciding whether an input is a palindrome or not has been proved to require $\Omega(\log n)$ space on a Turing machine. However, even storing the input takes space $n$ so doesn't ...
4
votes
1answer
124 views

Lower space bound on a turing machine accepting palindromes

Let $$ PAL = \lbrace x \in \lbrace 0, 1, \# \rbrace^* | x = rev(x) \rbrace $$ How do I show that a turing machine deciding $PAL$ must use space $\Omega(\log n)$? I have a feeling that I need to use ...
1
vote
1answer
427 views

Space complexity analysis of binary recursive sum algorithm

I was reading page 147 of Goodrich and Tamassia, Data Structures and Algorithms in Java, 3rd Ed. (Google books). It gives example of linear sum algorithm which uses linear recursion to calculate sum ...
2
votes
1answer
89 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 ...
3
votes
2answers
82 views

Find rectangle of minimum area where dimensions are larger than minimum

Problem: Given a collection $S$ containing $|S|=n$ rectangles defined by dimensions $(x,y)\in R^2$ (width and height of rectangles are real numbers), find the rectangles with the minimum area ($A_i = ...
-3
votes
1answer
46 views

Why is Mixed Quantified Horn SAT in PSPACE?

I want to prove that Mixed Quantified Horn SAT is a PSPACE-complete problem. I have proved that it is PSPACE-hard. How can I prove that it is in PSPACE? My study: To prove QSAT to be in PSPACE: ...
1
vote
1answer
71 views

Combined linked/array-like data structures for a set of non-intersecting sub-intervals of integer interval?

This question is related to my previous question: Looking for a set implementation with small memory footprint I'm looking for information about combined data structures, which can efficiently ...
1
vote
1answer
40 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
57 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 ...
1
vote
1answer
65 views

How to show that FPATH is in NL?

Consider this problem: $\qquad\displaystyle \mathsf{FPATH} = \{\langle G, a_1,\dots,a_n\rangle \mid G \text{ is a digraph with directed path } (a_1,\dots,a_n)\}$ It's allowed to visit nodes outside ...
0
votes
1answer
45 views

Finding dynamic programing algorithm

I got a matrix of integers of size $3\times n$. Of each one of the three rows, for each column I got to choose one number, with the restriction that, for each $i$, the numbers chosen in the $i$th and ...
0
votes
1answer
18 views

Local and Global storage with multithreading pools + locking threads

I am having difficulty answering the following questions relating to the use of threading. Question 1 is of relating to the possibility of a local storage per thread and a global storage accessible ...
1
vote
0answers
34 views

General object recognition versus specific object recognition

I have a question about the difference between general object detectors and specific object detectors. By specific object detectors, I'm referring to classifiers/object recognizers that are built to ...
2
votes
1answer
78 views

Why is the set of NFA that accept all words in co-NPSPACE?

In Sipser's book there is a section describing how to decide $\qquad\displaystyle \mathrm{ALL}_\mathrm{NFA} = \{ \langle N \rangle \mid N \text{ is an NFA}, L(N) = \Sigma^*\}$ in polynomial space. ...
1
vote
1answer
111 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 ...
3
votes
2answers
251 views

Has there been any more progress on P vs. PSPACE compared to P vs. NP?

I understand this is a slightly vague question, but there are results for P vs. NP, such as the question cannot be easily resolved using oracles. Are there any results like this which have been shown ...
-1
votes
0answers
20 views

pebbling is DSPACE($O(n^2)$) [closed]

Given a DAG $G$ and a vertex $v$ , consider the following game: We can place a pebble on a vertex $u$ if all its predecessors have pebbles on them. We can remove a pebble from a vertex any time. The ...
1
vote
0answers
207 views

Clique and PSPACE [closed]

I was wondering how I could go about creating an algorithm that gets all the cliques in a graph in PSPACE So far, based on some of the readings I've done, I am considering to use bit-strings (that ...
2
votes
1answer
62 views

What is the time/space complexity of $n!$? Can $n!$ has polynomial space complexity?

Given an integer $n$, calculate $n!=n\times(n-1)\times(n-2)\dotsc 3\times2\times1$. What is the best time and space complexity of calculating $n!$? P.S. I do not have any idea about this topic. I ...
2
votes
1answer
59 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 ...
2
votes
0answers
12 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 ...
1
vote
1answer
126 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
120 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)$, ...
3
votes
1answer
124 views

The crux of Savitch's Theorem

In "Introduction to the Theory of Computation" by Sipser, Savitch's theorem is explained as an improvement to a naive storage scheme for simulating non-deterministic Turing machines (NTM). I am going ...
2
votes
1answer
154 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 ...
2
votes
1answer
74 views

Language with $\log\log n$ space complexity?

We know that every non-regular language can be recognized with $ \Omega (\log\log n) $ space complexity. I'm looking for an example of a language which is $ \Theta (\log\log n) $ space complexity ...
1
vote
1answer
38 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)$ ...
4
votes
1answer
373 views

Relation of Space and Time in Complexity?

I'm looking for some clarification on some concepts/facts I came across while studying for a class. I was reading the following wikipedia article. The below specific section and statement intrigued ...
1
vote
1answer
81 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 ...
6
votes
2answers
218 views

Looking for a set implementation with small memory footprint

I am looking for implementation of the set data type. That is, we have to maintain a dynamic subset $S$ (of size $n$) from the universe $U = \{0, 1, 2, 3, \dots , u – 1\}$ of size $u$ with ...