Redundancy and Structure of computational problems

Question

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.

It was posted on TCS stackexchange without any answer.

Answer 1

In my experience, when a complexity (or computability) theorist talks about the "structure" of a class of languages, they are almost always using an informal notion which, while it may appreciated on an intuitive level by others who have studied the class, is currently beyond anyone's ability to formalize.

The widely-held belief that (say) $GI \ne NP$ comes as much from the few results we do have (e.g. that $GI$ is in the low hierarchy of $NP$) which would either have surprising consequences or would contradict other widely-held beliefs, as it does from the rather vaguer idea that there is "not enough structure" (or "too much structure"?) in $GI$.

"Redundancy" may be an easier notion to pin down formally, using say Kolmogorov complexity. But in a sense, the study of lower bounds is the study of redundancy (more specifically, the elimination of redundancy.) Given the difficult nature of proving lower bounds, I would expect formalizing the notion of redundancy to be equally difficult.