if DNA can encode everything the brain does with N bits of information, then regardless of how the DNA behaves, we have at least a loose estimate of the level of complexity in the brain
Non sequitur.
Solution to unified field theory. That's about 32 bytes of information, uncompressed. There, since that statement is so low in information content, it must be easy to find. We have a loose estimate of it's complexity with my statement, right?
Sure, and a shag rug has a much higher Kolmogorov complexity than the instructions for how to weave it. If measured carefully enough you'd find every individual strand of yarn in it has a unique length, orientation, curvature, amount of twist and amount of fraying that can be measured to an arbitrary degree of precision. So if you wanted to reproduce or store a description of that exact rug, you couldn't do it. That doesn't mean you can't make another rug that's just like it or close enough to serve the same purpose and be recognizable as a shag rug.
Like that rug, the brain contains oodles of complexity that doesn't matter at all for our purposes.
The question on the table, I think, is whether a brain that's pretty darn similar to a working one will still work or not - does it just have to have similar statistical properties, or are the explicit details of the connections important, does the chemistry have to be just-so, if we replaced neurons of type X with pseudo-neurons of type Y that do almost the same thing when viewed at scale Z but are completely different underneath, would it still work, etc.?
A lot of these questions are completely unanswered. We do know at least that the brain is extremely resilient to changes in chemistry and can work quite well even in the face of extensive damage, which is an indication that we might be surprised how little of the overall arrangement is actually necessary to keep it working properly.
We need to make sure that we're being careful with our language, too: the complexity necessary to specify any brain is a whole lot lower than the complexity to specify one particular brain. In AI the goal is the former, but for the latter, we really do have to worry about each strand in the carpet. An AI researcher might not give a rat's ass about reproducing your memories, and will be more than happy to construct something that can form any memories; on the other hand, to you, your memories (and the detailed wiring inside your head, which we might be able to alter substantially without "breaking" the brain) are vitally important.
That leads to 'seed AI', http://en.wikipedia.org/wiki/Seed_AI when run in reverse, so you'd have to implement the 'minimally viable self improving brain', and take it from there.
And even there maybe not all the strands in the carpet have to be just so, but it may very well be that there have to be certain amounts of each colour in roughly such and such a pattern with interconnects between these larger groups and so on. Some of that information is known but definitely not all of it.
The damage angle is a tricky one, some damage seems to be absolutely not problem at all, even if it is major, in other cases the smallest bit of damage seems to be enough to cause terminal failure. There are a lot of clues in there about the organization of the brain.
Non sequitur.
Solution to unified field theory. That's about 32 bytes of information, uncompressed. There, since that statement is so low in information content, it must be easy to find. We have a loose estimate of it's complexity with my statement, right?