Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > NL:
Reports tagged with NL:
TR98-023 | 16th April 1998
Eric Allender, Shiyu Zhou

#### Uniform Inclusions in Nondeterministic Logspace

We show that the complexity class LogFew is contained
in NL $\cap$ SPL. Previously, this was known only to
hold in the nonuniform setting.

more >>>

TR99-008 | 19th March 1999
Eric Allender, Vikraman Arvind, Meena Mahajan

#### Arithmetic Complexity, Kleene Closure, and Formal Power Series

The aim of this paper is to use formal power series techniques to
study the structure of small arithmetic complexity classes such as
GapNC^1 and GapL. More precisely, we apply the Kleene closure of
languages and the formal power series operations of inversion and
root ... more >>>

TR09-024 | 26th February 2009
Raghav Kulkarni

#### On the Power of Isolation in Planar Structures

The purpose of this paper is to study the deterministic
{\em isolation} for certain structures in directed and undirected
planar graphs.
The motivation behind this work is a recent development on this topic. For example, \cite{btv07} isolate a directed path in planar graphs and
\cite{dkr08} isolate a perfect matching in ... more >>>

TR13-004 | 11th November 2012
A. C. Cem Say, Abuzer Yakaryilmaz

#### Finite state verifiers with constant randomness

We give a new characterization of NL as the class of languages whose members have certificates that can be verified with small error in polynomial time by finite state machines that use a constant number of random bits, as opposed to its conventional description in terms of deterministic logarithmic-space verifiers. ... more >>>

TR17-052 | 19th March 2017
Dieter van Melkebeek, Gautam Prakriya

#### Derandomizing Isolation in Space-Bounded Settings

We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently reduce instances of computational problems to equivalent instances that have at most one solution? We present results for the NL-complete problem of reachability on digraphs, and for the LogCFL-complete problem of certifying acceptance ... more >>>

ISSN 1433-8092 | Imprint