Redundancy and Structure of computational problems It is widely believed that some computational problems such as graph isomorphism can not be NP-complete because it does not possess enough structure or redundancy to be computationally hard (NP-hard). I'm interested in the different formal notions for structure of computational problems and redundancy measures.

What are the major results known about such formal notions for computational problems? A recent survey  of such notions would be very nice.

EDIT: Posted on MathOverflow
Actually, I think that the phenomenon here is that GI in some sense has too much structure. It is in some ways the group-theoretic nature of its witnesses which leads to the $\mathsf{coAM}$ algorithm for GI and is one of the pieces of technical evidence why people believe GI is not $\mathsf{NP}$-complete. My thinking here is that there is so much structure that the problem is "too rigid" to encode arbitrary $\mathsf{NP}$ problems.

Another way to capture this is the fact that the counting and decision versions of GI are equivalent, whereas for all known $\mathsf{NP}$-complete problems this is not the case unless the polynomial hierarchy collapses. This can also be viewed as capturing some aspect of structure/redundancy: for unstructured, general problems, counting solutions seems to be much harder than telling if one exists, whereas the extensive structure of GI allows one to show that counting and decision are equivalent.

(On the other hand, group isomorphism seems even more structured than GI, yet no counting-to-decision reduction is known for group iso. Perhaps this says that GI is in sort of a "just right" level of structure - too structured to be NP-complete, but unstructured enough to allow a counting-to-decision reduction.)