Questions tagged [logspace]
The logspace tag has no usage guidance.
22
questions with no upvoted or accepted answers
22
votes
0
answers
755
views
What is the power of general poly-size permutation branching programs?
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions ...
- 5,038
17
votes
0
answers
496
views
What if an $\mathsf L$-complete problem has $\mathsf{NC}^1$ circuits? More generally, what evidence is there against $\mathsf{NC}^1=\mathsf{L}$?
Edit: let me reformulate the question in a more specific way (and change the title accordingly). A slightly edited version of the original question follows.
Is there a result comparable to the Karp-...
- 5,038
10
votes
0
answers
161
views
Alternative proofs of Savitch's theorem?
Question: Are there any known proofs of Savitch's theorem that $NL \subseteq L^2$ besides the usual one?
By the usual one I mean the proof based on recursively querying whether there is a midpoint.
...
- 1,439
9
votes
0
answers
718
views
Is it known if $\mathrm{CFL} \subseteq\mathrm{ NSPACE}(o(log^2(n)))$?
$\mathrm{CFL}$ is the class of context-free languages.
Question
Is $\mathrm{CFL}$ known to be solvable in $o(log^{2}(n))$ non-deterministic space? What about $\mathrm{DCFL}$?
- 5,025
6
votes
0
answers
230
views
What is the space complexity of computing the eigenvectors of a matrix?
By the answer to this question, computing the eigenvalues of a matrix to within $2^{-n}$ precision can be done in polylogarithmic space. Is it also possible to compute the eigenvectors of a matrix to ...
- 161
5
votes
0
answers
207
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 ...
- 12.6k
5
votes
0
answers
971
views
Any known connections between open problems for time and space: P vs L, NP vs NL, BPP vs BPL, ⊕P vs ⊕L
It would be nice to show that $P=L$ implies $NP=NL$. Or, $NP=NL$ implies $UP=UL$. Or maybe, $⊕P = ⊕L$ implies $PP = PL$.
Are there any known connections between the problems: P vs L, UP vs UL, NP ...
- 5,025
4
votes
0
answers
102
views
$\mathsf{NL}$ vs. $\mathsf{AC}^1$
It is known that $\mathsf{NL} \subseteq \mathsf{AC}^1$ (because $\mathsf{NL}$-complete problem PATH belongs to $\mathsf{AC}^1$).
Are there problems in $\mathsf{AC}^1$ that are unknown to be in $\...
- 1,859
4
votes
0
answers
96
views
Are there any non-relativized separations between $L$ and $PH$?
In one sense, $P$ vs. $PSPACE$ is the "easiest" first step to showing $P \neq NP$... and this is one you hear often about. In a different sense, you could take $L$ at one end and then $PH$ at the ...
- 757
3
votes
0
answers
113
views
What circuit depth is enough to compute a log-space complete problem?
To the best of my knowledge it is unknown that $\mathsf{L}$ is subset of $\mathsf{NC}^1$.
(Here $\mathsf{NC}^1$ is the class of decision problems solvable by a family of Boolean circuits, with ...
- 1,859
3
votes
0
answers
127
views
Is Circuit Minimization $P$-hard under logspace reductions?
By Circuit Minimization, I am referring to the following decision problem.
Circuit Minimization
Input: A bit string $x$ and a number $k$.
Question: Does there exist a Boolean Circuit $C$...
- 5,025
3
votes
0
answers
235
views
What is consequence of $PH\subseteq NSPACE((\log n)^2)$?
What is consequences of $PH\subseteq NSPACE((\log n)^2)$?
We don't even know PH is equals to L or not. I am wondering what will be happened when $PH\subseteq NSPACE((\log n)^2)$?
- 327
3
votes
0
answers
116
views
Restricted k-set cover is in NL or L
Restricted $k$-set cover:
Input: $(U,S_1,S_2,\cdots, S_n, k)$, $U=[n]$ and $S_i\subseteq U$ for all $1\leq i \leq n$.
Output: $\bigcap_{i\in I}S_i$ where $I=\{1,i_1,i_2\cdots,i_k\},
i_1=min(S_1),i_2=...
- 175
3
votes
0
answers
113
views
Number theoretic problems complete for $\mathsf{RL}$
Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$?
Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete ...
user34945
2
votes
0
answers
212
views
Simultaneous evidence for $L\neq NL$ and $P\neq NP$
We believe $L\neq NL$ and $P\neq NP$.
Is there any evidence which simultaneously imply $L\neq NL$ and $P\neq NP$?
- 12.6k
2
votes
0
answers
442
views
Is there any NC-complete problem with respect to logspace reduction?
The question is on the title.
We all know that $\text{NL}$ and $\text{P}$ have such problems. So I wonder the same thing about $\text{NC}$. More interestingly, is there any $k \ge 2$ and any $\text{...
- 169
2
votes
0
answers
326
views
Can Lexicographic BFS be implemented in logspace?
Input: Given graph $G=(V,E)$ vertex labeling in some order
Output: Change the labeling of vertices's such that
labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ ...
- 21
1
vote
0
answers
65
views
One way analogues of Logspace
When we say a function is one-way we typically mean a function is encodable in $P$ but its decryption is not in $P$ but in $UP$.
Likewise we say a function is logspace one-way if the function is ...
- 12.6k
1
vote
0
answers
85
views
Gurevich's theorem on primitive recursive functions being logspace-computable
I recently came across the following result attributed to Gurevich, according to which I understood that the class of problems solvable by primitive recursive functions is precisely the class L of ...
- 557
1
vote
0
answers
71
views
parametrized logspace algorithm for k-dominating set for planar graphs
$k$-Dominating set:
Given a graph $G=(V,E)$ where $V$ is a set of vertices and $E$ a set of edges, and an integer $k$, the $k$-Dominating set problem determines if there exists a subset of vertices $...
- 175
0
votes
0
answers
211
views
$CH=UL$ and partial breaking of transitive closure bottleneck problem and Savitch's theorem?
Let $L^t=DSPACE[O(\log n)^t]$, $NL^t=NSPACE[O(\log n)^t]$ and $UL^t=USPACE[O(\log n)^t$.
Savitch provides $NL\subseteq L^{2}$.
If $CH=UL$ we clearly got rid of the transitive closure bottleneck ...
- 12.6k
0
votes
0
answers
118
views
$\mathsf{ACC}^0$ and $\mathsf{TC}^0$ with $\mathsf{Cuniform}$-$\oplus\mathsf{L}$ or $\mathsf{Cuniform}$-$\mathsf{NC}^1$ oracle?
$\mathsf{TC}^0$ is a small class with $\oplus\mathsf{L}$ containing it.
Following inclusions are known:
$$\mathsf{Cuniform}\mbox{ -}\mathsf{ACC}^0\subseteq\mathsf{Cuniform}\mbox{ -}\mathsf{TC}^0\...
- 12.6k