Yes, I made that comment before I read the paper by Bazgan, Santha and Tuza. They mentioned in passing that the problem isn't NP-hard unless NP = coNP, and apparently felt that it was obvious enough to not require any further comment. I'm probably missing something obvious, but I can't quite follow this. With factorization (for example), a number's prime decomposition is unique and can serve as a certificate for both 'yes' and 'no' instances. For pigeonhole subset-sums equality, the solutions are not necessarily unique. It would depend on exactly how one crafted the corresponding decision problem, but it's not clear to me what the certificate would be for a 'no' instance.
login/create account
Drupal
CSI of Charles University
Re: A little more
Yes, I made that comment before I read the paper by Bazgan, Santha and Tuza. They mentioned in passing that the problem isn't NP-hard unless NP = coNP, and apparently felt that it was obvious enough to not require any further comment. I'm probably missing something obvious, but I can't quite follow this. With factorization (for example), a number's prime decomposition is unique and can serve as a certificate for both 'yes' and 'no' instances. For pigeonhole subset-sums equality, the solutions are not necessarily unique. It would depend on exactly how one crafted the corresponding decision problem, but it's not clear to me what the certificate would be for a 'no' instance.