21 votes
Accepted

Does space complexity analysis usually include output space?

Typically, we consider space complexity in terms of Turing machines with: one read-only input tape one write-only output tape however many read-write working tapes you want. The space usage is the ...
user avatar
19 votes

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

FOR x := 1 TO n DO FOR y := 1 TO n DO FOR z := 1 TO n DO IF E(x,y) && E(y,z) && E(z,x) THEN REJECT ACCEPT Each of the ...
user avatar
17 votes
Accepted

How is the problem, {⟨G⟩|G has no triangle} in Logspace?

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that ...
user avatar
  • 23.4k
16 votes
Accepted

why does LSPACE(log space) complexity class exist but not logtime?

Turing machines operating in logarithmic time cannot even read the entire input. This makes them rather uninteresting. What you have in mind is not Turing machines, but random-access machines, for ...
user avatar
15 votes
Accepted

What does sublinear space mean for Turing machines?

When dealing with restricted space, we use the following model. The Turing machine has three tapes: a read-only input tape, a read-write work tape, and a write-only output tape. We only measure space ...
user avatar
15 votes

Algorithms with O(sqrt(N)) SPACE complexity?

$\sqrt{n}$ space is somewhat unusual; the most likely reason for such a complexity to emerge is as a result of a so-called meet in the middle scheme. Two notable examples off the top of my head are ...
user avatar
  • 4,132
12 votes

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

Denote the arrays by $A,B$, and suppose they are of length $n$. Suppose first that the values in each array are distinct. Here is an algorithm that uses $O(1)$ space: Compute the minimum values of ...
user avatar
11 votes

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

Look up Blum's speedup theorem (yes, this article is less than informative; look at a book on complexity theory). It essentially says that there are programs for which there is a program doing the ...
user avatar
  • 13.6k
9 votes
Accepted

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

This algorithm doesn't run in polynomial time, it runs with polynomial delay. As the paper notes: Observe that the number of minimal, and even minimum solutions, can be exponential in the size of ...
user avatar
9 votes
Accepted

space complexity of DFA intersection problem

Solving intersection Non-Emptiness for 2 DFA's: It essentially just becomes a reachability problem for the product DFA. Roughly, we can solve it deterministically in $O(n^2)$ time using $O(n^2)$ ...
user avatar
9 votes

is Co-NP in PSPACE?

By the same reasoning that NP is in PSPACE, co-NP is in co-PSPACE. But co-PSPACE = PSPACE (you can just flip the answer), so co-NP is in PSPACE, too.
user avatar
9 votes
Accepted

Why is PH in PSPACE?

No, it is not necessary to remember all $y$'s tried before. In order to remember that I've tried the numbers $1,2,\ldots,200$, I do not need to remember $3,4,5,6,\ldots,199$. If you try them in order, ...
user avatar
9 votes
Accepted

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

You're basically there. If the machine uses at most $s(n)$ tape cells for inputs of length $n$, then it can't visit more than $C(n)=|Q||\Sigma|^{s(n)}s(n)$ different configurations (possible ...
user avatar
8 votes

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

The more well-known version of these questions is the $\mathsf{L} \stackrel?= \mathsf{NL}$ question. If $\mathsf{L} = \mathsf{NL}$ then a (slightly tricky) padding argument shows that $\mathsf{DSPACE}(...
user avatar
7 votes

Is FACTORIZATION or PRIMES known to be in LOGSPACE

Factoring is not known to be even in $\mathsf{P}$. Primality is not known to be in any class conjectured to be smaller than $\mathsf{P}$ (AFAIK).
user avatar
  • 21.7k
7 votes
Accepted

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

The classical example is $$(x_1 \lor y_1) \land (x_2 \lor y_2) \land \cdots \land (x_n \lor y_n)$$ which blows up to $2^n$ terms when converted to a DNF. Most functions have CNF and DNF complexity ...
user avatar
7 votes

Check for balanced parentheses in an expression in log-space

The Dyck language on any fixed number of symbols can be recognised by a marking automaton, which is a two-way finite automaton that can mark a fixed number of input tape squares. The automaton simply ...
user avatar
7 votes
Accepted

Is it possible to build a computer that would output $10^{10^{100}}$ symbols and halt, without using ~$10^{100}$ space?

The answer really depends on your computation model. On a (fixed) Turing machine, you can count up to $n$ using no space. A better formulation of the question is like this: Is there a function $f\...
user avatar
7 votes
Accepted

Can FPSPACE give exponentially long outputs?

Space classes always only include working space: the model is that we have a read-only input tape and write-only output tape, plus a read-write work tape (or multiple such tapes) on which we're only ...
user avatar
7 votes
Accepted

How hard are PSPACE-complete problems?

By definition, PSPACE consists of all languages decided by some Turing machine using polynomial space. So every language in PSPACE can be decided by some Turing machine using space $O(n^\ell)$ for ...
user avatar
7 votes
Accepted

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

The naive approach would be building histograms of both strings and checking whether they are the same. Since we are not allowed to store such a data structure (whose size would be linear to the size ...
user avatar
  • 599
7 votes
Accepted

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

Reduction from 3-SAT: a variable in 3-SAT becomes a character in your problem and is paired with its negation. Each clause becomes a word. e.g. 3 SAT: (a,b,-c) && (-b,c) => pairs: (a,-a), (...
user avatar
7 votes

$UCYCLE$ is in $L$

First of all, let me give the correct attribution to this algorithm: Cook and McKenzie, Problems complete for deterministic logarithmic space. The setup of Cook and McKenzie is that you are given an ...
user avatar
7 votes
Accepted

Show that NP is not equal to SPACE(n)

In order to prove that $\mathsf{SPACE}(n) \not\subseteq \mathsf{NP}$, you need to identify a language in $\mathsf{SPACE}(n)$ which is not in $\mathsf{NP}$. Not every language in $\mathsf{SPACE}(n)$ ...
user avatar
7 votes
Accepted

Logic behind O(n) solution for 'Maximum length sub-array having given sum'

This is an example of a dynamic algorithm. I will adapt the algorithm in the link, as I don't think that it is written in the most helpful way. Initialise sum = 0 ...
user avatar
  • 451
7 votes
Accepted

What's after EXPSPACE?

EXPSPACE is not the most inclusive computational complexity class. There's a huge number of complexity classes; see, e.g., the Complexity Zoo for some that have been studied (and in principle there ...
user avatar
  • 141k
7 votes

Difference between auxiliary space v/s space complexity

First consider the definitions below: $\mathbf{Auxiliary\space Space}$ is the temporary space allocated by your algorithm to solve the problem, with respect to input size. $\mathbf{Space \space ...
user avatar
  • 1,635
7 votes
Accepted

Space complexity for storing integers in Python

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the ...
user avatar
  • 1,319
6 votes
Accepted

Space complexity analysis of binary recursive sum algorithm

In a given tree, all the vertices of this tree correspond to binarySum() calls. The value of parameter n to ...
user avatar
  • 2,977
6 votes
Accepted

Prerequisites of computational complexity theory

Here are some prerequisites: Mathematical maturity. You get this by taking math courses. Mathematical induction. Important. Rudimentary calculus. That also includes all you need to know about big O ...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible