Redundancy and Structure of computational problems - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T23:18:55Z http://mathoverflow.net/feeds/question/109126 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109126/redundancy-and-structure-of-computational-problems Redundancy and Structure of computational problems Mohammad Al-Turkistany 2012-10-08T09:22:40Z 2013-01-24T16:22:00Z <p>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.</p> <p>What are the major results known about such formal notions for computational problems? A recent survey of such notions would be very nice.</p> <p>It was posted on <a href="http://cstheory.stackexchange.com/questions/12759/redundancy-and-structure-of-computational-problems" rel="nofollow">TCS stackexchange</a> without any answer.</p> http://mathoverflow.net/questions/109126/redundancy-and-structure-of-computational-problems/114876#114876 Answer by Chris Pressey for Redundancy and Structure of computational problems Chris Pressey 2012-11-29T12:30:45Z 2012-11-29T12:30:45Z <p>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.</p> <p>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\$.</p> <p>"Redundancy" may be an easier notion to pin down formally, using say Kolmogorov complexity. But in a sense, the study of lower bounds <em>is</em> 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.</p>