<p>Actually, I think that the phenomenon here is that GI in some sense has <em>too much</em> 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.</p>

<p>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.</p>

<p>(On the other hand, group isomorphism seems even <em>more</em> 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.)</p>

CC BY-SA 3.0
2013-09-06T17:20:54.183Z
So, GI in some sense is not "random" enough to capture NP-completness. Is there any formal notion that captures such lack of randomness of GI problem?
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-09-07T00:00:56.047Z
Yes, one such notion is that GI is not NP-complete! :-)  (Unless the polynomial hierarchy collapses.)
Scott Aaronson
CC BY-SA 3.0
2013-09-08T13:03:15.273Z
Jacobo Toran states "There is a common belief that GI does not contain enough structure or redundancy to be hard for NP", ON THE HARDNESS OF GRAPH ISOMORPHISM, SIAM Journal on Computing, 33(5), 1093–1108. The problem is that we don't know how to prove non NP-hardness of natural NP problems.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-09-08T14:07:19.337Z
I think perhaps Toran's statement and mine are two sides of the same coin: mine says that individual problem instances are *too* structured, and one result of that is that the overall language GI is not redundant enough (Toran's statement). I think. Without actually asking Jacobo it's hard to say.
Joshua Grochow
CC BY-SA 3.0
2013-09-06T15:48:11.790Z
2013-09-06T16:32:21.430Z
2013-09-06T16:32:21.430Z
Joshua Grochow
<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>EDIT: Posted on <a href="https://mathoverflow.net/questions/109126/redundancy-and-structure-of-computational-problems">MathOverflow</a></p>

<cc.complexity-theory><graph-isomorphism>
Redundancy and Structure of computational problems
Mohammad Al-Turkistany
# Redundancy and Structure of computational problems

(Asked by: username_0 on 2012-09-27)

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](https://mathoverflow.net/questions/109126/redundancy-and-structure-of-computational-problems)

**Tags:** cc.complexity-theory, graph-isomorphism


---

## 1 answers

### Answer by username_1 on 2013-09-06. Score: 4

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.)

> **Comments:**
> **username_0**: So, GI in some sense is not "random" enough to capture NP-completness. Is there any formal notion that captures such lack of randomness of GI problem?  
> **username_2**: Yes, one such notion is that GI is not NP-complete! :-)  (Unless the polynomial hierarchy collapses.)  
> **username_0**: Jacobo Toran states "There is a common belief that GI does not contain enough structure or redundancy to be hard for NP", ON THE HARDNESS OF GRAPH ISOMORPHISM, SIAM Journal on Computing, 33(5), 1093–1108. The problem is that we don't know how to prove non NP-hardness of natural NP problems.  
> **username_1**: I think perhaps Toran's statement and mine are two sides of the same coin: mine says that individual problem instances are *too* structured, and one result of that is that the overall language GI is not redundant enough (Toran's statement). I think. Without actually asking Jacobo it's hard to say.  

---

