6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ Thanks Yuval. That second direction eluded me, since I was trying to find a "meaningful" reduction from any $L \in P$ to $B \in NL$, I didn't think of building a simple artificial reduction such as you described. $\endgroup$ – Cauthon Aug 31 '15 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.