Given a 2SAT instance can we convert into bipartite perfect matching in parsimonious reduction?
$\begingroup$
$\endgroup$
9
-
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$– Yuval FilmusOct 12, 2021 at 20:13
-
$\begingroup$ 2SAT is NL complete and unambiguous BPM is UL complete and NL=UL is conjectured. $\endgroup$– TurboOct 12, 2021 at 20:14
-
$\begingroup$ Would the existence of such a reduction imply that NL=UL? $\endgroup$– Yuval FilmusOct 12, 2021 at 20:15
-
$\begingroup$ What kind of reduction are you interested in? Logspace? $\endgroup$– Yuval FilmusOct 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$– TurboOct 12, 2021 at 20:17
|
Show 4 more comments