@cmuratori @Jonathan_Blow It's both, right? Complete = Hard + NP, and it's clearly P to verify the length of a purported solution.
@tom7 @Jonathan_Blow Current CS research, as far as I'm aware, thought it already proved that was impossible, so it'd be major news.
-
-
@cmuratori@Jonathan_Blow if it's not in NP (=P time verifier) then you're right. It seemed easy to me though. Maybe I made a mistake there. -
@tom7@Jonathan_Blow Well, the hope would be that it actually is easy to you, because then P=NP! Go try and make sure you can't solve it :) - Show replies
New conversation -
-
-
@cmuratori@Jonathan_Blow is it maybe because edge weights can be arbitrarily large so binary search on bin search on the sol len isn't P? -
@tom7@Jonathan_Blow So, I mispoke - they did NOT prove that it was impossible. They proved _the verifier_ was NP-complete. - Show replies
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.