Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?

  • 1
    $\begingroup$ This question is coming out of the blue. Why would you expect such a reduction to exist? Have you attempt to construct one, or to show that one cannot exist, perhaps conditional on some known hardness assumption? $\endgroup$ Oct 12, 2021 at 20:13
  • $\begingroup$ 2SAT is NL complete and unambiguous BPM is UL complete and NL=UL is conjectured. $\endgroup$
    – Turbo
    Oct 12, 2021 at 20:14
  • $\begingroup$ Would the existence of such a reduction imply that NL=UL? $\endgroup$ Oct 12, 2021 at 20:15
  • $\begingroup$ What kind of reduction are you interested in? Logspace? $\endgroup$ Oct 12, 2021 at 20:16
  • $\begingroup$ Logspace is great but I believe an uniform DLOGTIME AC0 reduction exists. It would demonstrate BPM is hard for NL which is known I think (reason the uniform DLOGTIME AC0 reduction should exist) and indeed complete for NL since checking BPM is in AC0. $\endgroup$
    – Turbo
    Oct 12, 2021 at 20:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.