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

CC BY-SA 3.0
2012-01-23T19:43:05.150Z
2012-01-23T19:43:05.150Z
Glauber De Bona
<p><a href="http://en.wikipedia.org/wiki/Graph_automorphism_problem" rel="nofollow">Graph automorphism problem</a> ( 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}). </p>

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

CC BY-SA 3.0
2011-10-30T17:28:34.670Z
We don't have any reasonable general lowerbounds even for NP-complete problems, and I can't recall any result that rules out [GNI](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) being in P. Can you tell what we know conditionally about lowerbounds (conditional or otherwise) about the deterministic computational complexity of GNA?
Kaveh
CC BY-SA 3.0
2011-10-30T18:47:06.333Z
@Kaveh, I guess even polynomial (or even super-linear) lower bounds are not known.
Mohammad Al-Turkistany
CC BY-SA 3.0
2011-10-31T14:56:19.930Z
Conditional upper bound: Klivans-van Melkebeek (http://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
CC BY-SA 3.0
2011-10-31T18:42:10.180Z
@JoshuaGrochow make this an answer ?
Suresh Venkat
CC BY-SA 3.0
2011-10-31T22:40:10.557Z
Thanks for the upper bounds. @SureshVenkat, I'm looking for lower bounds :)
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-05-12T12:56:38.620Z
@JoshuaGrochow sorry I don't get it. doesn't babai's algorithm qive quasi poly proofs? does this improve anything what you wrote?
Turbo
CC BY-SA 3.0
2017-05-12T13:02:33.163Z
@Turbo: everything I wrote is still true, and Babai's algorithm gives an unconditional quasi-polynomial certificate.
Joshua Grochow
<cc.complexity-theory><graph-isomorphism><proof-complexity><automorphism>
Best lower bound for proof complexity of graph non-automorphism problem
Mohammad Al-Turkistany
# Best lower bound for proof complexity of graph non-automorphism problem

(Asked by: username_0 on 2011-10-29)

[Graph automorphism problem](http://en.wikipedia.org/wiki/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)?

**Tags:** cc.complexity-theory, graph-isomorphism, proof-complexity, automorphism
> **Comments:**
> **username_1**: We don't have any reasonable general lowerbounds even for NP-complete problems, and I can't recall any result that rules out [GNI](http://en.wikipedia.org/wiki/Graph_isomorphism_problem) being in P. Can you tell what we know conditionally about lowerbounds (conditional or otherwise) about the deterministic computational complexity of GNA?  
> **username_0**: @Kaveh, I guess even polynomial (or even super-linear) lower bounds are not known.  
> **username_2**: Conditional upper bound: Klivans-van Melkebeek (http://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.  
> **username_3**: @JoshuaGrochow make this an answer ?  
> **username_0**: Thanks for the upper bounds. @SureshVenkat, I'm looking for lower bounds :)  
> **username_4**: @JoshuaGrochow sorry I don't get it. doesn't babai's algorithm qive quasi poly proofs? does this improve anything what you wrote?  
> **username_2**: @Turbo: everything I wrote is still true, and Babai's algorithm gives an unconditional quasi-polynomial certificate.  

---

## 1 answers

### Answer by username_5 on 2012-01-23. Score: 1

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.


---

