# Best lower bound for proof complexity of graph non-automorphism problem

Graph automorphism problem ( GA) of determining whether a graph has a nontrivial automorphism is a good candidate for a problem in NP-intermediate. I'm looking for references that study the certificate complexity of graph non-automorphism (GNA= {G| G is rigid or asymmetric graph}).

What is the best known lower bound on the length of certificates that proves a graph is rigid ($G \in GNA$)? Also, Is there a plausible conjecture that prohibits sub-exponential certificates for Co-NP-complete problems (analogues to ETH)?

• We don't have any reasonable general lowerbounds even for NP-complete problems, and I can't recall any result that rules out GNI being in P. Can you tell what we know conditionally about lowerbounds (conditional or otherwise) about the deterministic computational complexity of GNA? – Kaveh Oct 30 '11 at 17:28
• @Kaveh, I guess even polynomial (or even super-linear) lower bounds are not known. – Mohammad Al-Turkistany Oct 30 '11 at 18:47
• Conditional upper bound: Klivans-van Melkebeek (dx.doi.org/10.1137/S0097539700389652) show that $GNI$ (and also $GNA$, since it is in $AM$) has subexponential size proofs unless $EXP = \Sigma_3^P$. They also give a condition under which $AM = NP$, in particular, under which $GNI$ and $GNA$ have polynomial-size proofs. – Joshua Grochow Oct 31 '11 at 14:56
• @JoshuaGrochow make this an answer ? – Suresh Venkat Oct 31 '11 at 18:42
• @Turbo: everything I wrote is still true, and Babai's algorithm gives an unconditional quasi-polynomial certificate. – Joshua Grochow May 12 '17 at 13:02