Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [space-time-tradeoff]

The tag has no usage guidance.

3
votes
1answer
203 views

Conesequences of $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$

Does $\forall k\in \mathbb N \space NP\not\subseteq TISP(poly(n),n^k)$ has any separation of classes or consequences? My main question is can use this to show that $P \neq NP$ or some thing useful ...
2
votes
1answer
51 views

Counting reversibly using few FullAdders and little work space

Given N bits on a reversible computer, I want to compute their Hamming weight (into a binary register) while using a minimal number of FullAdder circuits (takes 3 bits, outputs their sum as 2 bits) ...
7
votes
2answers
286 views

Are space and time hierarchies even comparable?

I am wondering if there are any results to what extent the space and time hierarchies "disagree" on which problem is harder. For example, is it known whether there are languages $L_1$ and $L_2$ such ...
5
votes
0answers
89 views

Is $\mathrm{DTISP}(n^a,n^b) \subseteq \mathrm{DSPACE}(n^{b/2})$?

The title question arose in the course of discussing a question on MathOverflow. Obviously, from the space hierarchy theorem we know that not only is it false that $\mathrm{DSPACE}(n^b) \subseteq \...
4
votes
1answer
151 views

What is known about computing distinct count range queries?

Let $U=\{1,\ldots, u\}$ be a universe of elements for some $u\in \mathbb N$. Given some $n\in\mathbb N$, we are interested in computing some function $f:U^{\le n}\to\mathbb R$ over range queries. In ...
5
votes
0answers
145 views

On space complexity of permanent modulo $2^t$?

We know from here that permanent of $0/1$ matrix modulo $2^t$ is in $DTIME(n^{t+3})$ and hence in $P$. My question is whether permanent of $0/1$ matrix modulo $2^t$ is in $L$ as well or is the current ...
2
votes
0answers
118 views

Space time lower bound with $\mathsf{PSPACE}$ oracle

Does a single tape Turing machine with access to $\mathsf{PSPACE}$ oracle needs more than $\mathsf O(1)$ working tape memory and $\mathsf O(1)$ working time to solve $\mathsf{NP}$-complete problem? ...
3
votes
1answer
330 views

What is the best way to find an induced cycle basis of a graph?

My question is essentially what comes in the subject line: what is the best way to find an induced cycle basis of a graph (i.e., a cycle basis of the graph in which each cycle is an induced subgraph ...
18
votes
1answer
697 views

Edit distance in sublinear space

What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input? I assume the input is ...
9
votes
2answers
525 views

Computing a transitive completion / path existance oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
19
votes
3answers
2k views

How much time to recognize palindromes in logarithmic space?

It is well-known that palindromes can be recognized in linear time on $2$-tape Turing machines, but not on single-tape Turing machines (in which case the time needed is quadratic). The linear-time ...
8
votes
1answer
265 views

Storing a bit vector in uninitialized memory and minimal space

A well-known trick for storing bit vectors using uninitialized memory can allocate a bit vector of size $n$ in which all of the bits are set to $0$ by allocating $(2 n + 1)\lceil \lg n \rceil$ bits of ...
8
votes
2answers
2k views

Space complexity to compute the optimal string alignment for the Levenshtein edit distance

If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (...
13
votes
1answer
3k views

Need a good overview for Succinct Data Structure algorithms

(already asked on main site, but asking also here for better coverage, sorry) Since I knew about Succinct Data Structures I'm in a desperate need of a good overview of most recent developments in ...
14
votes
1answer
217 views

Early history of certain results on space-time tradeoffs?

I'm interested in the early history of published results on general-purpose space-time tradeoffs. In particular, I want to know who first described the following type of algorithm for evaluating a ...
8
votes
1answer
261 views

Hamming weight of powers

Given positive integers $b$ and $e$, what is known about the space and time complexity of finding the Hamming weight (number of binary 1s) of $b^e$? If $e\log b$ bits are available, the number can ...
13
votes
2answers
2k views

Space-time tradeoff and the best algorithm

Consider some language $L$ such that: $L \in DTIME(O(f(n))) \cap DSPACE(O(g(n)))$ and so that $L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n)))$ In other words, the fastest machine $M$ computes $L$ ...
17
votes
3answers
1k views

Efficient logspace algorithms

It is easy to see that any problem that is decidable in deterministic logspace ($L$) runs in at most polynomial time ($P$). Many known logspace algorithms (For example : undirected st-connectivity, ...
13
votes
1answer
668 views

Space-time tradeoff lower bounds

Following the discussion on lower bounds for 3SAT [1], I'm wondering what are the main lower bound results formulated as space-time tradeoffs. I'm excluding results such as, say, Savitch's theorem; a ...