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