Yes, the r- result is for worst case (the approx algo has to guarantee a result that is r times the optimal, in all cases). That's why I say this particular definition of approx may not be a very good one.
But what if similar results hold for other criteria of approximation? Then "P=NP approximately" would imply "P=NP exactly". A better definition of approx might require to distribute probabilities over all instances of an NP-hard problem, say SAT. That space may be infinite but countable -- I'll check. Since the P=?NP question is equivalent to the SAT ∈? P question, we only need to consider SAT. My intuition is this: if we have an algo that can approx NP good enough for many *general* cases, then why would it become impossible to approx NP for *all* cases? And if we can approx NP in polynomial time for all cases, then it should be that P = NP. ------------------------------------------- AGI Archives: https://www.listbox.com/member/archive/303/=now RSS Feed: https://www.listbox.com/member/archive/rss/303/21088071-f452e424 Modify Your Subscription: https://www.listbox.com/member/?member_id=21088071&id_secret=21088071-58d57657 Powered by Listbox: http://www.listbox.com
