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
