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

  • 1
    $\begingroup$ 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? $\endgroup$ – Kaveh Oct 30 '11 at 17:28
  • $\begingroup$ @Kaveh, I guess even polynomial (or even super-linear) lower bounds are not known. $\endgroup$ – Mohammad Al-Turkistany Oct 30 '11 at 18:47
  • 5
    $\begingroup$ 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. $\endgroup$ – Joshua Grochow Oct 31 '11 at 14:56
  • $\begingroup$ @JoshuaGrochow make this an answer ? $\endgroup$ – Suresh Venkat Oct 31 '11 at 18:42
  • 1
    $\begingroup$ @Turbo: everything I wrote is still true, and Babai's algorithm gives an unconditional quasi-polynomial certificate. $\endgroup$ – Joshua Grochow May 12 '17 at 13:02

If GNA is in CoNP, and by certificate you mean any string y such that x is in GNA iff xy is accepted by a deterministic turing machine in polynomial time, then a non-trivial lower bound on the certificate size would imply P!=NP. If P=NP, then CoNP=NP=P and there is a deterministic turing machine that accepts GNA without the need of a certificate, or with a certificate whose size is equal to zero.


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.