NP completeness and the singularity
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.