Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR09-082 | 1st April 2022 09:17

A combinatorial property of #L assuming NL=UL and its implications for ModL

RSS-Feed




Revision #1
Authors: T.C. Vijayaraghavan
Accepted on: 1st April 2022 09:17
Downloads: 242
Keywords: 


Abstract:

We first show that SLDAGSTCON which is the $st$-connectivity problem for simple layered directed acyclic graphs, where the vertex $s$ is in the $1^{st}$ row and the vertex $t$ is in the last row of the input graph, is complete for NL under logspace many-one reductions. Let $G=(V,E)$ be a directed graph given as input and let $s,t\in V$. Also let $p$ be a positive integer whose unary representation can be computed by a deterministic $O(\log |G|)$ space bounded Turing machine. Then we can determine if the number of directed paths from $s$ to $t$ in $G$ is at least $(p+1)$ in FNL. Otherwise if the number of directed paths from $s$ to $t$ in $G$ is lesser than $(p+1)$ then the FNL machine outputs the number of directed paths from $s$ to $t$ in $G$. This in turn shows that verifying if there are polynomially many accepting computation paths for a NL machine on a given input is in FNL. Assume that NL =UL. Let $\Sigma$ be the input alphabet, $f\in #L$ and $g\in FL$ such that, for the given input string $x\in\Sigma ^*$, $g(x)$ is a positive integer $k$ in the unary representation. Then we show that the function ${{f(x)}\choose {k}}\in \sharpL$. In this paper we obtain consequences of this combinatorial property of #L for the complexity class ModL defined in \cite[Definition 3.1]{AV2010}. We prove the following characterization of ModL: assuming NL =UL, we show that for every language $L\in$ ModL, there exists a function $f\in$ #L and a function $g\in$
FL such that on any input $x$, we have
\begin{itemize}
\item $g(x)=0^p$ for some prime $p$, and,
\item if $x\in L$ then $f(x)\equiv 1(\mod p)$,
\item if $x\not \in L$ then $f(x)\equiv 0(\mod p)$.
\end{itemize}
As a result, assuming NL =UL, we are able to show that
\begin{enumerate}
\item ModL is the logspace analogue of the complexity class ModP defined by K\"obler and Toda in \cite[Definition
3.1]{KT1996}, and
\item ModL is closed under complement.
\end{enumerate}



Changes to previous version:

The title has been changed. The entire article has been rewritten. This revised version has been published in the International Virtual Conference on Advances in Data Sciences and Theory of Computing (ICADSTOC-2022), pages 51-56, Bharath Institute of Higher Education and Research, 2022. ISBN: 978-93-5607-750-8.


Paper:

TR09-082 | 20th September 2009 16:32

Characterization of ModL using Prime Modulus.





TR09-082
Authors: T.C. Vijayaraghavan
Publication: 24th September 2009 15:34
Downloads: 3468
Keywords: 


Abstract:

The complexity class ModL was defined by Arvind and Vijayaraghavan in [AV04] (more precisely in Definition 1.4.1, Vij08],[Definition 3.1, AV]). In this paper, under the assumption that NL =UL, we show that for every language $L\in ModL$ there exists a function $f\in \sharpL$ and a function $g\in FL$ such that on any input string $x$, we have
1. $g(x)=0^p$ for some prime $p$, and,
2. if $x\in L$ then $f(x)\equiv 1(\mod p)$,
3. if $x\not \in L$ then $f(x)\equiv 0(\mod p)$.

As a consequence under the assumption that NL=UL we show that
1. $\ModL$ is the logspace analogue of the complexity class $ModP$ defined by K\"obler and Toda in \cite[Definition 3.1,KT96], and that
2. $\ModL$ is closed under complement.

We prove the characterization of ModL stated above by showing the following property of $\sharpL$. Assuming NL =UL, if $f\in \sharpL$ and $g\in FL$ such that $g(x)$ is a positive integer $k$ in unary that depends on the input $x$ then the function
${{f(x)}\choose{k}} \in \sharpL$.



ISSN 1433-8092 | Imprint