ECCC-Report TR09-082https://eccc.weizmann.ac.il/report/2009/082Comments and Revisions published for TR09-082en-usFri, 01 Apr 2022 09:17:07 +0300
Revision 1
| A combinatorial property of #L assuming NL=UL and its implications for ModL |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2009/082#revision1We 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}Fri, 01 Apr 2022 09:17:07 +0300https://eccc.weizmann.ac.il/report/2009/082#revision1
Paper TR09-082
| Characterization of ModL using Prime Modulus. |
T.C. Vijayaraghavan
https://eccc.weizmann.ac.il/report/2009/082The 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$.Thu, 24 Sep 2009 15:34:17 +0300https://eccc.weizmann.ac.il/report/2009/082