Consider $\Pi$ to be the problem to decide if there is a subset of numbers that sum to $0$ in the given list of integers.

How does one construct a promise problem equivalent to $xSAT$ from this? $xSAT$ is in $NP\cap coNP$.

How is it possible that the original problem was NP complete and the transformed problem is in coNP?

Doesn't this mean NO instances also have short certificates for the original problem $\Pi$?

  • $\begingroup$ By xSAT, do you mean Exact 1-in-3-SAT? If so, where do you get that $xSAT \in NP \cap coNP$? $\endgroup$ – Realz Slaw Oct 28 '13 at 16:08
  • 1
    $\begingroup$ On Promise Problems in memory of Shimon Even (1935{2004) Oded Goldreich $\endgroup$ – T.... Oct 28 '13 at 16:09
  • $\begingroup$ PDF $\endgroup$ – Realz Slaw Oct 28 '13 at 16:58
  • $\begingroup$ Goldreich's paper is about promise problems, so NP doesn't quite have its usual meaning. You'll have to give us more context if you want any more help, but I would suggest you first read Goldreich's paper yourself. $\endgroup$ – Yuval Filmus Nov 13 '16 at 11:25
  • $\begingroup$ @YuvalFilmus this was in 2013 (need to recollect). $\endgroup$ – T.... Nov 15 '16 at 9:08

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.