The ability to solve NP-complete problems seems to be dependent on the concept of information overhead. It's explained a bit in the theory paper here: http://arxiv.org/pdf/1405.0931.pdf

One concern I have is in section VI-A. The author refers to the ability to read out of a collection of memory elements the sum of their contents. Since the sums are totally defined by the other numbers it doesn't seem that you can count those bits as additional information. Maybe I'm missing something, though. The bit after on Exponential Information Overhead seems more robust.