Constructing a promise problem equivalent to XSAT from subset sum

Brout 09/24/2018 at 06:52. 0 answers, 0 views
complexity-theory reductions

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$?

No Answers Yet


Popular Tags