Is there a missed connection between entropy and circuit complexity? It looks like one might be able to draw some parallels between the two.
Other thoughts; it's interesting that PvsNP is essentially about the lengths of proofs, and thus it is the task of deciding in poly time whether you can decide all decidable problems whose proofs are polynomial to their encoding.