So, I finally have a bona-fide theoretical result. I finished a proof that the Blocker problem is NP-hard (and the corresponding decision problem is NP-Complete). I'm not going to publish it here just yet because, like I said, this one is for real I don't want to get scooped. It does significantly improve the chances of my Blocker paper getting published.
While I'm withholding the specifics for the moment, I will say that sometimes it does help to think about the dual space of the problem. Once I turned it into a maximization rather than minimization problem, it practically solved itself. The proof is quite concise.
No comments:
Post a Comment