Questions tagged [logspace]
The logspace tag has no usage guidance.
51
questions
31
votes
1
answer
903
views
Treewidth and the NL vs L Problem
ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in ...
- 10.6k
26
votes
2
answers
961
views
What are the consequences of $L = \oplus L$?
Shiva Kintali has just announced a (cool!) result that graph isomorphism for bounded treewidth graphs of width $\geq 4$ is $\oplus L$-hard. Informally, my question is, "How hard is that?"
We know ...
- 6,994
22
votes
0
answers
773
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,273
17
votes
0
answers
506
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,273
15
votes
1
answer
473
views
Complexity of the search version of 2-SAT assuming $\mathsf{L = NL}$
If $\mathsf{L = NL}$, then there is a logspace algorithm that solves the decision version of 2-SAT.
Is $\mathsf{L = NL}$ known to imply that there is a logspace algorithm to obtain a satisfying ...
user6973
15
votes
1
answer
812
views
Hardness of Computing Weisfeiler-Lehman labels
The 1-dim Weisfeiler-Lehman algorithm (WL) is commonly known as canonical labeling or color refinement algorithm. It works as follows :
The initial coloring $C_0$ is uniform, $C_0(v) = 1$ for all ...
- 10.6k
15
votes
1
answer
283
views
Does ${\bf AC^0PAD} = {\bf PPAD}$?
What happens if we define ${\bf PPAD}$ such that instead of a polytime Turing-machine/polysize circuit, a logspace Turing-machine or an ${\bf AC^0}$ circuit encodes the problem?
Recently giving ...
- 13.9k
15
votes
1
answer
613
views
Log-space reduction from Parity-L to CNOT circuits?
Question.
In their paper Improved simulation of stabilizer circuits, Aaronson and Gottesman claim that simulating a CNOT circuit is ⊕L-complete (under logspace reductions). It is clear that it ...
- 8,821
14
votes
1
answer
368
views
What are the consequences of $P \subseteq L/poly$?
A language is in $L/poly$ if there exists a logspace Turing machine that decides the language with polynomial amount of advice.
See here for more info: https://en.wikipedia.org/wiki/L/poly
...
- 5,127
13
votes
1
answer
513
views
What are the obstructions to extending $L=SL$ to $L=NL$?
Omer Reingold's proof that $L=SL$ gives an algorithm for USTCON (In an Undirected graph with special vertices $s$ and $t$, are they Connected?) using only logspace. The basic idea is to build an ...
- 807
13
votes
1
answer
298
views
Large classes which contain LOGSPACE for which strict inclusions are unknown
The wikipedia page on PSPACE mentions that the inclusion $NL\subset PH$ is not known to be strict (unfortunately without references).
Q1: What about $L\subset PH$ and $L\subset P^{\#P}$ - are these ...
- 301
12
votes
1
answer
352
views
A super-linear time problem in NL
It is a well-known fact that $ \mathsf{NL} = \cup_{k>0} \mathsf{2NFA[k]} $, where $ \mathsf{2NFA[k]} $ is the class of languages recognized by two-way nondeterministic finite automata with $ k>0 ...
- 3,707
10
votes
1
answer
232
views
On sparse complete sets and P vs L
Mahaney's Theorem tells us that if there is a sparse $NP$-complete set under polynomial-time many-one reductions, then $P = NP$. (See "Sparse complete sets for NP: Solution of a conjecture of Berman ...
- 5,127
10
votes
1
answer
182
views
It is known that $L \subsetneq PH$?
Is it known whether $Logspace$ is strictly contained in the polynomial time hierarchy ?
Are there oracles relative to which these classes are equal / distinct ?
- 296
10
votes
0
answers
167
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
1
answer
222
views
$BPL$ with polylog random bits is in $L$
Consider a $BPL$ machine (namely, a probabilistic algorithm that uses logspace and polynomially many random bits). It is known (Saks-Zhou) that $BPL \subseteq DSPACE(log^{1.5}(n))$.
My question is ...
- 383
9
votes
1
answer
400
views
Two way deterministic multihead counter automata or logspace TM with counter
Is that known something about languages recognized by two-way deterministic multihead counter automaton or logspace TM with counter (equivalent model)? This class called Aux2DC in my advisor's paper. ...
9
votes
1
answer
839
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,127
7
votes
1
answer
200
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,127
6
votes
1
answer
701
views
What are the consequences of solving XOR 3-SAT in Logspace?
XOR Formulas
Consider boolean formulas with connectives $\wedge$ (AND) and $\oplus$ (XOR). Such a boolean formula is a valid instance for XOR SAT if it is a conjunction of $\oplus$-clauses. An $\...
- 5,127
6
votes
1
answer
4k
views
k-Vertex Cover problem is in parameterized Log space
$k$-Vertex Cover:
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$-Vertex Cover problem determines if there exists a subset of vertices $...
- 175
6
votes
2
answers
631
views
Complexity of comparison unary>binary
What is the smallest widely-known complexity class to which
$$\left\{\langle i,j\rangle\middle|\begin{array}{@{}l@{\ }l@{}} & i\ \text{is a unary encoding of a positive integer}\ \hat\imath\\\...
user44501
6
votes
0
answers
237
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
6
votes
0
answers
470
views
Can we show that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? [closed]
We know by Immerman–Szelepcsényi theorem that $\mathsf{NL}=\mathsf{coNL}$? Does it follow from this theorem that $\mathsf{NL}^\mathsf{NL} = \mathsf{NL}$? Here, $\mathsf{NL}^\mathsf{NL}$ denotes the ...
- 87
5
votes
1
answer
195
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,973
5
votes
1
answer
480
views
Can Lexicographic BFS be implemented in logspace?
Input: Given graph $G=(V,E)$ with vertices labeled in some order
Output: Change the labeling of vertices such that the
labeling starts $v_1$ as $u_1$. Next, label the neighbors of $v_1$ as $u_2,u_3,...
- 51
5
votes
0
answers
231
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.8k
5
votes
0
answers
1k
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,127
4
votes
1
answer
232
views
Can $L=SL$ be shown with the replacement product instead of the zig-zag product?
(This is a bit of follow-up to https://cstheory.stackexchange.com/posts/comments/93266 but is a distinct enough question I though it should be on its own.)
In Omer Reingold's logspace USTCON ...
- 807
4
votes
0
answers
106
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,973
4
votes
0
answers
98
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 ...
- 807
3
votes
1
answer
466
views
NFA to 2DFA: what are the upper and lower bounds?
Suppose that one has an NFA (from, say, a regular expression). What is the state complexity of turning it into a 2DFA?
- 516
3
votes
0
answers
244
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
545
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{...
- 179
3
votes
0
answers
118
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
114
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
1
answer
2k
views
Detecting undirected cycles in logarithmic space [closed]
I have a lot of difficulties with constructing algorithms that use $O(\log n)$ space, as I am unsure about how much can be stored on the worktape.
I am trying to figure out an algorithm for the ...
- 131
2
votes
0
answers
106
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 ...
- 871
2
votes
0
answers
213
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.8k
1
vote
2
answers
1k
views
Why NL is not L
I'm a beginner in learning complexity and get confused at NL.
NL is the class of languages that are decidable in logarithmic space on a nondeterministic Turing machine. In other words, NL = NSPACE($\...
1
vote
0
answers
85
views
Perm and Det mod $2^k$ - II
Given a $0/1$ square matrix, the permanent and determinant modulo $2^k$ is in $\oplus P$ and $\oplus L$ respectively for any fixed $k$. In fact both are in $\oplus L$ (in fact in $\oplus SPACE(k^2\log ...
- 12.8k
1
vote
0
answers
72
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.8k
1
vote
0
answers
64
views
Reference to "compressibility" of logarithmic space [closed]
Is there a reference somewhere for the result SPACE($O(\log n)$) = SPACE($\log n$)? i.e. Big-O doesn't matter in logspace since you can compress the space. I feel like this is an elementary result but ...
- 21
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
1
answer
102
views
Complexity status of restricted k-clique [closed]
Restricted $k$-clique:
Input: $(G,v,k)$ where $v$ is vertex in $V$
Output: k-clique containing vertex $v$.
What is the space and time complexity status of this Restricted $k$-clique problem?
Is ...
- 175
0
votes
1
answer
183
views
Comparing SAT to MCSP reduction class separations and faster SAT class separations?
Assume $SAT$ is in $QuasiP$. We immediately infer $NQuasiP=QuasiP$ and $EXP=NEXP$. From https://people.csail.mit.edu/rrw/easy-witness-nqp.pdf we infer $NQuasiP$ is not in $P/poly$ which implies $...
- 12.8k
0
votes
0
answers
56
views
Is there a construction which multiplies and adds spanning trees in Logspace?
I.1 Suppose we have two planar graphs $G_1$ and $G_2$ with spanning tree count $C_1$ and $C_2$ respectively then is there a graph construction in Logspace to get a planar graph from $G_1$ and $G_2$ ...
- 12.8k
0
votes
0
answers
222
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.8k
0
votes
0
answers
120
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.8k
-2
votes
1
answer
304
views
Closure properties of $L$ (DLOGSPACE)? [closed]
What are the closure properties of $L$ (DLOGSPACE)? I'm not only intrested in these properties (if of course $S$ and $T$ are in $L$) :
$S \cap T$
$S^*$ (kleene-star)
$S.T$ (concat)
- 151