11 ms·
I always wondered if we could could find something in nature that shows P=NP. It could be bacteria, autistic savants, dna computing, etc. Has anyone set up a
by tocomment 17y ago
I always wondered if we could could find something in nature that shows P=NP. It could be bacteria, autistic savants, dna computing, etc. Has anyone set up a test like this?
I'm thinking you simply increase the number and inputs on an NP problem and watch at what rate the time taken by one of these methods increases. (Is this too naive of an approach?)
- zitterbewegung 17y agoHere is something that scientists have studied which does this http://www.tjhsst.edu/~rlatimer/techlab06/Students/OuyangPaper06F.pdf http://www.tjhsst.edu/~rlatimer/techlab06/Students/OuyangPap... They actually take the approach that you state. They also have to judge how the system solved the problem. If you don't reach an optimal state you could be only approximating P=NP.
- tocomment 17y agoThat's an interesting paper. I wonder why we can't make a "soap surface" computer? Just translate your NP-Complete program into a Steiner tree problem, make the appropriate glass plates and pegs model, get the results and translate back? I wish I knew more computer science. I'd love to try it.
- zitterbewegung 17y agoYou could do that exactly. The problem is that the soap surface computer doesn't always perform the task to find the best steiner tree etc...
- tocomment 17y agoWhy is that? Is it approximating then, or just unreliable?
- zitterbewegung 17y agoUnreliable it doesn't necessarily give the best steiner tree or a good answer. Sort of hazy on this mainly just googled this information.
- tocomment 17y agoThat's a shame. I wonder if we could find other natural processes like this? I wonder if electricity seeming to instantly know the path of least resistance could be wired up to solve traveling salesman somehow?
- nopassrecover 17y agoProtein folding?