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 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
