Log in

NP completeness and the singularity - Journal of Omnifarious

Oct. 16th, 2009

12:09 pm - NP completeness and the singularity

Previous Entry Share Next Entry

In many books about the singularity, the idea comes up of having your thought processes run on some interesting and imaginative substrate. Say, as an emergent property of a flock of pigeons. While this might well be possible, I think NP completeness places some hard limits on exactly what an external observer can determine about such systems.

There is an interesting problem that might be NP complete called the graph isomorphism problem. The graph isomorphism problem deals with proving that two different graphs have a one-to-one mapping showing them to be a simple transformation of each other.

So, if you have two different entities claiming to be the same entity running on a different substrate it's very hard to tell if they really are unless they tell you the mapping.

A plot element in some post-singularity novels is the idea of someone hiding themselves in various places by having themselves run on a wide variety of unusual substrates. A sort of steganography of consciousness. If the graph isomorphism problem is NP complete, then finding entities of human-level complexity who are doing this is likely practically impossible. Even the resources of a matrioshka brain are likely not enough to do the computation required to find them.

Current Location: 2237 NW 62nd ST, 98107
Current Mood: [mood icon] contemplative


[User Picture]
Date:October 16th, 2009 08:04 pm (UTC)
This is a sexy post.
(Reply) (Thread)
[User Picture]
Date:October 16th, 2009 09:11 pm (UTC)

I'm glad you think so. :-)

(Reply) (Parent) (Thread)