wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> general problem-solving / chatting / whatever >> NP-complete Problems and Physical Reality
        
(Message started by: amichail on Mar 10^th, 2005, 1:31am)

Title: NP-complete Problems and Physical Reality
Post by amichail on Mar 10^th, 2005, 1:31am

Can NP-complete problems be solved efficiently in the physical universe?

Here's a nice survey on the topic that includes soap bubbles and protein folding:

http://ideas.web.cse.unsw.edu.au/index.php?module=articles&func=display&ptid=1&aid=447

Title: Re: NP-complete Problems and Physical Reality
Post by towr on Mar 10^th, 2005, 2:46am

on 03/10/05 at 01:31:06, amichail wrote:

Can NP-complete problems be solved efficiently in the physical universe?

The physical universe seems to do a good job of it so far. ::)
And quantum computing certainly has some promise to it.