6
$\begingroup$

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

Improve this question
$\endgroup$
7
  • 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
    Commented Oct 30, 2011 at 17:28
  • $\begingroup$ @Kaveh, I guess even polynomial (or even super-linear) lower bounds are not known. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Oct 30, 2011 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
    Commented Oct 31, 2011 at 14:56
  • $\begingroup$ @JoshuaGrochow make this an answer ? $\endgroup$
    – Suresh Venkat
    Commented Oct 31, 2011 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
    Commented May 12, 2017 at 13:02

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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