But r-approximate is still worst-case complexity, right? To the extent the human mind can solve NP-complete problems, it does so in a roughly "probably approximately correct" manner -- i.e. most of the time it can get a pretty good solution.... This is quite different than getting within some factor of r of the correct solution every time...
-- Ben On Tue, Feb 25, 2014 at 3:46 PM, YKY (Yan King Yin, 甄景贤) < [email protected]> wrote: > On Tue, Feb 25, 2014 at 3:19 PM, Ben Goertzel <[email protected]> wrote: > >> >> Hmmm... >> >> >>> . But if approximate solutions exist, then it seems natural that we can >>> throw more resources at it to get it closer and closer to exact solutions. >>> It is unlikely that exact solutions would abruptly become impossible. >>> >> >> >> Hmmm. Among other issues, that really depends on how much more resources >> you need to throw at a problem, to get each additional epsilon of >> accuracy... no? >> > > > There're these "hardness of approximability" results that say, for > example, to design an r-approximate algorithm with small r would still > imply that P = NP. > > By r-approximate it means the algorithm can find a solution whose cost is > r times the optimum. [ Trevisan 2004: "Inapproximability of combinatorial > optimization problems" ] > > Though I suspect there're other [better?] criteria of approximation that > can be defined... but the result may be the same, ie, approximate > polynomial-time solution would imply exact polynomial-time solution. > > =) > *AGI* | Archives <https://www.listbox.com/member/archive/303/=now> > <https://www.listbox.com/member/archive/rss/303/212726-deec6279> | > Modify<https://www.listbox.com/member/?&;>Your Subscription > <http://www.listbox.com> > -- Ben Goertzel, PhD http://goertzel.org "In an insane world, the sane man must appear to be insane". -- Capt. James T. Kirk ------------------------------------------- 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
