MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.