@tom7 @Jonathan_Blow Therefore, it is _NP-hard_ (harder than NP-complete), NOT NP-complete. It is a _harder_ class of problems.
-
-
Replying to @cmuratori
@tom7@Jonathan_Blow Another way to think of it would be that if someone proves P=NP, NP-complete problems _become_ P problems, right.1 reply 0 retweets 0 likes -
Replying to @cmuratori
@tom7@Jonathan_Blow NP-hard problems DO NOT become P problems! They are still impossible to solve exactly, _EVEN IF_ P turns out to be NP.1 reply 0 retweets 0 likes -
-
Replying to @cmuratori
@tom7@Jonathan_Blow So a problem _can't_ be "both" NP-complete and NP-hard. It is only one or the other.2 replies 0 retweets 0 likes -
Replying to @cmuratori
@tom7@Jonathan_Blow And if you actually do know of an in-P way to verify and answer to traveling salesman, you really need to tell us!!!1 reply 0 retweets 0 likes -
Replying to @cmuratori
@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.2 replies 0 retweets 0 likes -
Replying to @cmuratori
@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.1 reply 0 retweets 0 likes -
Replying to @tom7
@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 :)2 replies 0 retweets 0 likes -
Replying to @cmuratori
@cmuratori@Jonathan_Blow I'll read up. In portmantout, edge weights are bounded by problem size. Thanks for pointing out my mistake! :)1 reply 0 retweets 0 likes
@tom7 @Jonathan_Blow Let me know what the answer turns out to be!
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.