I'm trying to prove that some problem, A, is in NL. I have found a logspace reduction from A to 2-SAT - am right in thinking that this is not sufficient to prove that A is in NL?

If so, how does one formally go about proving that a language is in NL - is the only way we can do this by providing some deciding non-deterministic TM for A that only uses logspace?

  • $\begingroup$ In fact, any problem logspace reducible to a problem in NL is itself in NL. The proof is similar to the analogous statement for L. $\endgroup$ – Yuval Filmus Dec 11 '18 at 0:31

Your Answer

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

Browse other questions tagged or ask your own question.