@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
@cmuratori@tom7@Jonathan_Blow np-hard should mean "at least as hard as np-complete", not necessarily "harder", as far as i understand2 replies 0 retweets 0 likes -
Replying to @supermoof
@supermoof@tom7@Jonathan_Blow Hmm - yeah, OK, I think you are right about that - so we haven't _yet_ proved that they are harder...1 reply 0 retweets 0 likes -
Replying to @cmuratori
@supermoof@tom7@Jonathan_Blow ... just that we know they are at least as hard.1 reply 0 retweets 0 likes -
Replying to @cmuratori
@supermoof@tom7@Jonathan_Blow I think everything else I said is correct though.1 reply 0 retweets 0 likes -
Replying to @cmuratori
@supermoof@tom7@Jonathan_Blow Ie., traveling salesman is not NP-complete and does not have a P-verifier.1 reply 0 retweets 1 like
@supermoof @tom7 @Jonathan_Blow Here's the Wikipedia diagram, too :)pic.twitter.com/qNJtoDJh7h
-
-
Replying to @cmuratori
@supermoof@tom7@Jonathan_Blow Yes, and Wikipedia also confirms that Traveling Salesman is not NP-complete. It's NP-hard...1 reply 0 retweets 0 likes -
Replying to @cmuratori
@supermoof@tom7@Jonathan_Blow ... and its _verifier_ is NP-complete (ie., verification), not P.0 replies 0 retweets 0 likes
End of conversation
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.