patternMinor
Prove or disprove that $NL$ is closed under polynomial many-one reductions
Viewed 0 times
polynomialclosedproveunderthatonereductionsmanydisprove
Problem
If $B \in NL$ and there exists a Karp reduction (polynomial-time many-one reduction) from $A$ to $B$, then $A \in NL$.
Prove that the above claim is correct, incorrect, or equivalent to an open question.
Trying to solve this, I was pretty sure that the statement is either incorrect, or at least equivalent to an open question. My reasoning was that the statement is correct if the reduction is promised to be a log-space reduction (uses only $log \ n$ space). Removing this demand seems to be too much, but I wasn't able to prove this.
I was then told that this statement is equivalent to the open question $NL = P$. I thought of this, and tried proving that if the statement is correct, then one can define a Karp reduction from any $L \in P$ to a language in $NL$, therefore proving $L \in NL$ and $P \subseteq NL$. However I couldn't find such a reduction.
The only reduction I could think of that could help would be to transform the operations of a deterministic polynomial Turing machine $M_L$ to a configurations graph (a directed graph with an edge $(u,v)$ iff there exist two consecutive configurations $u, v$ in $M_L$. However, this reduction would take exponential $2^{p(n)}$ time, and not polynomial.
Any contribution would be appreciated.
Prove that the above claim is correct, incorrect, or equivalent to an open question.
Trying to solve this, I was pretty sure that the statement is either incorrect, or at least equivalent to an open question. My reasoning was that the statement is correct if the reduction is promised to be a log-space reduction (uses only $log \ n$ space). Removing this demand seems to be too much, but I wasn't able to prove this.
I was then told that this statement is equivalent to the open question $NL = P$. I thought of this, and tried proving that if the statement is correct, then one can define a Karp reduction from any $L \in P$ to a language in $NL$, therefore proving $L \in NL$ and $P \subseteq NL$. However I couldn't find such a reduction.
The only reduction I could think of that could help would be to transform the operations of a deterministic polynomial Turing machine $M_L$ to a configurations graph (a directed graph with an edge $(u,v)$ iff there exist two consecutive configurations $u, v$ in $M_L$. However, this reduction would take exponential $2^{p(n)}$ time, and not polynomial.
Any contribution would be appreciated.
Solution
Let's prove the two directions separately. Suppose first that $\mathsf{NL}=\mathsf{P}$. In order to prove the statement, suppose that $B \in \mathsf{NL}$ and that there is a polytime many-one reduction from $A$ to $B$. Since $\mathsf{P}$ is closed under polytime many-one reductions and $B \in \mathsf{NL} = \mathsf{P}$, clearly $A \in \mathsf{P} = \mathsf{NL}$, proving the statement.
Suppose next that the statement is correct. Let $B$ be any non-trivial language in $\mathsf{NL}$ (for example, $B = \{\epsilon\}$), and let $A \in \mathsf{P}$ be arbitrary. Since $A \in \mathsf{P}$ there is a polytime function $f$ computing it. We can easily modify $f$ to a polytime reduction from $A$ to $B$ by fixing some YES instance and NO instance in $B$ (here we need that $B$ be non-trivial). The statement implies that $A \in \mathsf{NL}$. Since $A$ was arbitrary, we deduce that $\mathsf{P} \subseteq \mathsf{NL}$ and so $\mathsf{NL} = \mathsf{P}$.
Suppose next that the statement is correct. Let $B$ be any non-trivial language in $\mathsf{NL}$ (for example, $B = \{\epsilon\}$), and let $A \in \mathsf{P}$ be arbitrary. Since $A \in \mathsf{P}$ there is a polytime function $f$ computing it. We can easily modify $f$ to a polytime reduction from $A$ to $B$ by fixing some YES instance and NO instance in $B$ (here we need that $B$ be non-trivial). The statement implies that $A \in \mathsf{NL}$. Since $A$ was arbitrary, we deduce that $\mathsf{P} \subseteq \mathsf{NL}$ and so $\mathsf{NL} = \mathsf{P}$.
Context
StackExchange Computer Science Q#45736, answer score: 4
Revisions (0)
No revisions yet.