Asymptotic analyses of the space needed to run algorithms.

learn more… | top users | synonyms

3
votes
1answer
30 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 ...
5
votes
1answer
77 views

Why do we reject turing machines that use space less than the log of the length of the input?

In Computational complexity: Modern Approach by Arora and Barak, it's mentioned that We will require however that $S(n)> \log n$ since the work tape has length $n$, and we would like the ...
1
vote
0answers
18 views

Space-time tradeoffs for deterministic logarithmic space algorithms

I have several algorithms that map read-only input into write-only output utilizing only logarithmic space with pointer arithmetic. While the algorithms have a very small $O(\log^c{}n)$ critical path ...
1
vote
1answer
99 views

Prove or disprove that DTIME(n^2)=NL

I need to prove or disprove $DTIME(n^2)=NL$. It kind of feel obvious that I need to disprove it, because if I have non-deterministic machine $M$ that uses $\log n$ space, then it meets at most $|Q| n\...
0
votes
1answer
37 views

Relating memory complexity and decidablity

Given a language $L_u$, about which we know that there exists a non-deterministic turing machine which accepts it (as in, implying $L_u \in RE$) with memory complexity of $c^{p(n)}$, where $c$ is a ...
3
votes
1answer
86 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 ...
1
vote
0answers
23 views

Why do we set conditions f(n) ≥ n resp. f(n) ≥ log(n) the Time resp. Space Hierarchy?

In the Space (Time) Hierarchy Theorem and also fully space (time) constructibility of two function we have the condition: being greater than $log(n)$ (being greater than $n$). Why do we have these ...
2
votes
0answers
45 views

Hamming numbers for $O(N)$ speed and $O(1)$ memory

Disclaimer: there are many questions about it, but I didn't find any with requirement of constant memory. Hamming numbers is a numbers $2^i 3^j 5^k$, where $i$, $j$, $k$ are natural numbers. Is ...
0
votes
1answer
37 views

Space complexity of Horner's method

Following is the excerpt from wiki If numerical data are represented in terms of digits (or bits), then the naive algorithm also entails storing approximately $2n$ times the number of ...
3
votes
1answer
30 views

Replacing n with 2n in asymptotic bounds

I am going through Normal Subgroup Reconstruction and Quantum Computation Using Group Representations by Hallgren et al. In the proof of the theorem $6$ of the paper on page 632, the authors go on ...
3
votes
1answer
65 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
65 views

Verifiers equivalent classes

This is a HW question, so Im not expecting full solutions or anything, but would love some direction. Also English is not my first language, so I apologize in advance. We define a new class of ...
0
votes
1answer
47 views

PSPACE and DTIME $2^{cn}$

This is a HW question that I'm stuck on and was hoping for some help. we're supposed to prove that: PSPACE not equals DTIME($2^{cn}$) for every $c>0$ (or actually for the union of all $c>0$)
3
votes
1answer
83 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 ...
1
vote
2answers
68 views

Is it true that P is not equal to deterministic linear space complexity class?

I'm curious, how could I know that P (polynomial time complexity class) is not equal to deterministic linear space complexity class? Is there some proof? Or should I find some algorithm which is not ...
1
vote
0answers
29 views

(Why) is there no complexity class for linear space (O(n))? [duplicate]

tldr: I'm looking for any general information about the linear space complexity class. e.g. is there a complete problem for it? the Quantified Boolean Formula (QBF) problem is a P-space complete ...
3
votes
0answers
32 views

Ordered set transformation data structure

Assume an ordered set $M = \{\tau_1, \tau_2, ..., \tau_n\}$ and a subset $S = \{\tau_k,\tau_l,...,\tau_m\}\subset M$ where $1\leq k,l,m \leq n$. All the items of $S$ are randomly ordered. The task is ...
2
votes
1answer
26 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).
4
votes
2answers
273 views

NSPACE for checking if two graphs are isomorphic

I was studying nondeterministic Turing Machines and came across the following question: Describe a nondeterministic Turing Machine (NTM) that only accepts two graphs (G1 and G2) if they are ...
3
votes
1answer
60 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 ...
0
votes
1answer
44 views

Certificate Definition of NL

As per the Sanjeev Arora book, for a certificate based definition of $NL$, the machine is allowed a "read-once" certificate tape to store the certificate along with $O(log n)$ read/write work tape for ...
4
votes
1answer
57 views

Acceptance behavior of L and NL with and without cycling

The complexity class NL seems to allow cycling, otherwise we wouldn't have SL $\subset$ NL. What about L? If an algorithm from L cycles for a given input, it certainly cannot accept (because it won't ...
1
vote
2answers
53 views

Counting all $x,y,z$ such that $a[x] > a[y] + a[z]$

Given an array $a$, I want to count all triplets of indices $x,y,z$ such that $a[x] > a[y] + a[z]$. I can think of two solutions: Go over all triplets of indices $x,y,z$ directly. This takes ...
3
votes
1answer
43 views

How is the space hierarchy theorem different for non space constructible functions?

Sipser first introduces space constructible functions. Then uses the definition to prove the space hierarchy theorem: if f(n) is a space constructible function then there are languages that can ...
1
vote
1answer
48 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 ...
1
vote
1answer
57 views

L closed under logspace reduction

Given two languages $A$ and $B$ I have been asked to show that, if $B \in L$ and we have a logspace reduction $f$ from $A$ to $B$ then $A \in L$. I read the proof that $L$ is closed under logspace ...
8
votes
1answer
190 views

Is there an algorithm for algorithms time/space complexity optimisation?

In 1950s a number of methods for circuit minimization for Boolean functions have been invented. Is there an extension of those methods or anything similar for optimising time or space complexity of ...
1
vote
0answers
71 views

Space Complexity

This particular code is written in C. ...
1
vote
1answer
65 views

Is HAMPATH in NL/L?

I know HAMPATH is NP complete problem. But is there a way to tell if it is either a NL or L problem? I tried searching a lot of places online but it feels like I am going nowhere. Thanks in advance ...
3
votes
1answer
51 views

is Co-NP in PSPACE?

Is Co-NP in PSPACE? I think it should obviously be, but I just wanted to make sure. I can find that NP is in PSPACE in Internet, but not on Co-NP.
3
votes
2answers
130 views

Proof of APSPACE = EXP

I have been reading Computational Complexity A Modern Approach book and this proof wasn't given in the book. Please give a semi-detailed proof of this. I have found a paper which has this proof(by ...
4
votes
1answer
81 views

space complexity of DFA intersection problem

the DFA-intersection computation problem, given two DFAs specified on the input, compute the intersection DFA, or the decision problem to determine its emptiness, turns out to have wider/ deeper ...
2
votes
1answer
30 views

How to denote the space complexity in terms of output

Normally the space complexity of an Algorithm $A$ is denoted $\textrm{SPACE}(A)$, which means how much space is needed by the computation itself. I would however like to also describe how much storage ...
2
votes
1answer
42 views

Time complexity of minimizing Boolean expression

Given any arbitrary boolean expression using AND, OR and NOT gates what is the time complexity of minimizing the expression such that minimum number of gates are used. The following Wikipedia article ...
2
votes
1answer
53 views

Can a cellular automata structure simulates another cellular automata structure?

In Elementary Cellular Automata, rules can show one pattern, but i am wondering if there is something where a cellular automata structure can simulate another structure? Is there a category for this ...
4
votes
1answer
177 views

Prove or disprove that $NL$ is closed under polynomial many-one reductions

If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$. Prove that the above claim is correct, incorrect, or equivalent to an open ...
5
votes
1answer
97 views

Is L closed under linear-time reductions?

L is as usual the complexity class DSPACE($\log n$), of languages decidable using a deterministic Turing machine using logarithmic workspace. Is L closed under linear-time reductions? It is ...
1
vote
1answer
123 views

Extra space of MergeSort [duplicate]

Here is my implementation of mergeSort. I need n extra space for the helper array. But what about recursive calls? I call sort ...
-1
votes
1answer
98 views

Find the 10 top most occurring strings in a huge array of objects

Find the 10 top most occurring strings in a huge array of Strings. Since the array is huge, it is not possible to load it in memory completely. My idea is to parse the arrays one by one and put the ...
6
votes
1answer
104 views

TM recognizing $0^n1^n$ requires Ω(log n) space

I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires $\Omega(\text{log }n)$ space. I believe this can be ...
0
votes
0answers
17 views

How to calculate Space Complexity of function? [duplicate]

I've understtod the basic that if i've a function like this int sum(int x, int y, int z) { int r = x + y + z; return r; } requires 3 units of space for the ...
1
vote
0answers
171 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
1answer
133 views

PSPACE languages reducible to other PSPACE languages in polynomial space

Intuitively it makes sense that all PSPACE languages are reducible to other PSPACE languages in polynomial space. But how would I go about actually showing this?
3
votes
1answer
124 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 ...
2
votes
0answers
308 views

PSPACE completeness, with different kinds of reductions [closed]

PSPACE-complete$_{FP}$ problems are the PSPACE problems such that every other PSPACE problem can be transformed to it with a polynomial time reduction, i.e. the reduction is an algorithm $\in$ FP. ...
1
vote
1answer
55 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 $\omega$-...
1
vote
0answers
64 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, ...
2
votes
1answer
41 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
40 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
444 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 ...