The tag has no wiki summary.

learn more… | top users | synonyms

8
votes
1answer
111 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 ...
12
votes
0answers
131 views

What evidence is there against $\mathsf{NC}^1=\mathsf{L}$?

I am having trouble finding in the literature (or online) a discussion of the relationship between $\mathsf{NC}^1$ and logarithmic space going beyond "the former is included in the latter and it is ...
12
votes
1answer
206 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 ...
1
vote
1answer
82 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 ...
6
votes
1answer
180 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. ...
7
votes
0answers
187 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 ...
10
votes
1answer
218 views

Ruzzo-Simon-Tompa oracle access mechanism

In a paper on relativizing logspace computations, Ladner and Lynch construct an oracle relative to which $\mathsf{NL} \nsubseteq \mathsf{P}$. There are some more pathological examples in this vein in ...
14
votes
1answer
525 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 ...
29
votes
1answer
739 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 ...
5
votes
0answers
392 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 ...
13
votes
1answer
300 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 ...
25
votes
2answers
704 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 ...