12
$\begingroup$

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

Improve this question
$\endgroup$
4
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Mohammad Al-Turkistany Sep 6 '13 at 17:20
  • 1
    $\begingroup$ Yes, one such notion is that GI is not NP-complete! :-) (Unless the polynomial hierarchy collapses.) $\endgroup$ – Scott Aaronson Sep 7 '13 at 0:00
  • $\begingroup$ 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. $\endgroup$ – Mohammad Al-Turkistany Sep 8 '13 at 13:03
  • $\begingroup$ 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. $\endgroup$ – Joshua Grochow Sep 8 '13 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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