@tom7 @Jonathan_Blow My understanding is that NP-complete means that it has been proven to have a polynomimal-time answer verifier.
@tom7 @Jonathan_Blow So, I mispoke - they did NOT prove that it was impossible. They proved _the verifier_ was NP-complete.
-
-
@tom7@Jonathan_Blow So traveling salesman _could_ still become P-verifiable someday if P=NP. -
@tom7@Jonathan_Blow But at the moment, we don't know any P-verifier because we still think P != NP. - 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.