If you have a solver for an L in NP do you have enough information to build a solver for co-L in Co-NP? Meaning, is there a procedure that can take you from a solver for one to a solver for another?

  • $\begingroup$ This is equivalent to whether NP equals coNP. $\endgroup$ – Yuval Filmus Dec 1 '20 at 16:12
  • $\begingroup$ @YuvalFilmus how this is true is not entirely clear to me? I do not mean to say the languages L and co-L are equivalent in complexity. Maybe the procedure that takes you from one solver to the other takes a very long time or it always produces a solver that takes a lot longer to compute? I just mean to ask if one has the information content of the other. $\endgroup$ – user129081 Dec 1 '20 at 16:14
  • $\begingroup$ Oh, I see - I got it wrong. If a language is in NP then its complement is in coNP. The “solver” (usually called verifier) is essentially identical. $\endgroup$ – Yuval Filmus Dec 1 '20 at 16:30
  • $\begingroup$ Can you edit your question to define what you mean by a "solver", specifically? Do you want everything to run in polynomial time? $\endgroup$ – D.W. Dec 1 '20 at 20:25

Your Answer

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