<p>First, (as has now been edited into the question statement) a positive answer to your question would immediately improve the state of the art in worst-case bounds for graph isomorphism. For a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm yields a $2^{O(\sqrt{n})}$-time deterministic algorithm, but the current best known for GI is only $2^{O(\sqrt{n \log n})}$ </p>

<p>Second, it is not even immediately clear to me whether or not the current best algorithm is in fact a $O(\sqrt{n \log n})-\mathsf{PTIME}$ algorithm, although the first part of it clearly is, in some sense. The algorithm first guesses a set of vertices of size $\sqrt{n/\log n}$ to individualize (Zemlyachenko's trick - see <a href="http://dx.doi.org/10.1007/3-540-10854-8_4">here</a> for an exposition in English), which can be done by guessing $\sqrt{n \log n}$ bits nondeterministically. However, after guessing those and individualizing (in deterministic poly time), it applies the best-known bounded-degree isomorphism test, which takes time $n^{O(d /\log d)}$ (Theorem 9.1 of <a href="http://dx.doi.org/10.1109/SFCS.1983.10">this paper</a>), and applies it in the case of $d=O(\sqrt{n \log n})$. I'd have to think carefully about whether the latter algorithm could be turned into a $O(\sqrt{n \log n})-\mathsf{PTIME}$ algorithm (seems like an interesting question...)</p>

CC BY-SA 3.0
2014-04-11T14:39:18.427Z
Do you have links to versions not behind a paywall? I have never seen an actual implementation of Zemlyachenko's trick or the bounded degree isomorphism test. Partitioning vertices by degree like NAUTY speeds things up, but those with the same degree you still have to check all prime cycle permutations on them AFIK.
Chad Brewbaker
CC BY-SA 3.0
2014-04-11T17:10:50.970Z
@Chad: I'm unfortunately not aware of non-paywalled versions of those articles. However, Zemlyachenko's trick is quite simple to implement in practice and essentially reduces the degree. For practical implementation of Zemlyachenko's trick, i think the only question is the trade-off between enumerating sets of vertices to individualize (exponential in the size of the set) and any potential gains made by effectively reducing the degree. I do not know if it is actually implemented in NAUTY or other practical isomorphism algorithms.
Joshua Grochow
CC BY-SA 3.0
2014-04-11T17:55:57.820Z
@Chad: By the way, testing prime cycle permutations only suffices for detecting a nontrivial automorphism; it does not suffice for testing isomorphism. For example, if $G$ is a graph without nontrivial automorphisms, let $\pi$ be *any* permutation - not necessarily a prime cycle. Then $\pi(G)$ is isomorphic to $G$, and $\pi$ is the *only* isomorphism between $G$ and $\pi(G)$. But this isomorphism would not be detected by only considering prime cycles.
Joshua Grochow
CC BY-SA 3.0
2014-04-11T19:58:31.853Z
At the cost of doubling $n$, ISO can be computed with AUT by putting both graphs in an adjacency matrix.
Chad Brewbaker
CC BY-SA 3.0
2014-04-11T21:23:30.067Z
@Chad: If you do that, then there are already $n!$ prime-cycle permutations of order 2, so you've lost any potential savings. This is related to the fact that the reduction you describe is from ISO to computing a *generating set* for the automorphism group. There is no known poly-time reduction from ISO to the problem of merely deciding whether a graph has a nontrivial automorphism.
Joshua Grochow
CC BY-SA 3.0
2014-04-12T03:12:04.073Z
NAUTY stands for No AUTomorphoisms Yes?  McKay is going about it the canonical form matching way.
Chad Brewbaker
CC BY-SA 4.0
2019-12-31T08:05:16.027Z
@JoshuaGrochow Is $NTIME(n)$ same as $n-PTIME$ here?
VS.
CC BY-SA 4.0
2019-12-31T08:09:00.203Z
@VS. I don't think so. For example, $n$-PTIME includes languages decidable by an algorithm which uses n nondeterministic bits and takes $O(n^2)$ time, but $\mathsf{NTIME}(n)$ (probably) does not include all such languages.
Joshua Grochow
CC BY-SA 4.0
2021-03-16T23:08:04.700Z
@JoshuaGrochow What is the complement of $\beta P$ (should be $\beta$ conondeterministic bits and in $P$) and is it identical to $\beta' P$ at a relation between $\beta$ and $\beta'$?
Turbo
CC BY-SA 4.0
2021-03-17T05:18:06.213Z
The complement is as you say, and I don't understand the second part of your question.
Joshua Grochow
CC BY-SA 4.0
2021-03-18T02:13:41.987Z
@JoshuaGrochow I think $\beta$ and $\beta'$ are exponentially related in $\overline{\beta P}\subseteq \beta'P$ if $\beta=\Omega(n)$ if $coNP\not\subseteq NP$ but if $\beta=o(n)$ it is unclear.
Turbo
CC BY-SA 4.0
2021-03-18T02:31:23.560Z
I don't think anything better than exponential is known. You should be able to relate it to standard classes like coNP using padding, but I'd have to think about it a bit.
Joshua Grochow
CC BY-SA 3.0
2014-04-11T02:33:19.797Z
2014-04-11T02:33:19.797Z
Joshua Grochow
<p><em>Bounded nondeterminism</em> associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$.  This class consists of those languages that are accepted by some nondeterministic Turing machine $M$ obeying the same resource bounds as are used to define $C$, but where $M$ is allowed to make at most $g(n)$ nondeterministic moves.  (I am using the notation of Goldsmith, Levy and Mundhenk, instead of the original by Kintala and Fischer, and $n$ is the size of the input.)</p>

<p>My question:</p>

<blockquote>
  <p>Is there a constant $c\ge0$ such that GRAPH ISOMORPHISM is in $c\sqrt{n}$-$\mathsf{PTIME}$?</p>
</blockquote>

<p>(<em>Edit:</em> Joshua Grochow pointed out that a positive answer to this question would imply an algorithm for GI that has better asymptotic runtime bounds than are currently known.  I would therefore be happy to relax the bound, allowing $o(\sqrt{n}\log n)$ nondeterministic moves.)</p>

<hr>

<h2>Background</h2>

<p>For every fixed constant $c \ge 0$, $\mathsf{PTIME} = {c\log n}$-$\mathsf{PTIME}$, as $c\log n$ nondeterministic moves create at most a polynomial number of configurations to explore deterministically.  Moreover $\mathsf{NP} = \cup_c n^c\text{-}\mathsf{PTIME}$, and by means of padding one can exhibit NP-complete languages in $n^\varepsilon$-$\mathsf{P}$ for every $\varepsilon &gt; 0$.</p>

<p>Kintala and Fischer observed that deciding if an input graph with vertices $V$ has a $(|V|/3)$-clique is $\mathsf{NP}$-complete, but is in $O(\sqrt{n})$-$\mathsf{PTIME}$.  To see this, discard the vertices which have at most $|V|/3 - 2$ neighbours.  If there are too few remaining vertices, then reject.  Otherwise the remaining vertices form a graph of size $\Omega(|V|^2)$.  Then guess a $|V|/3$-subset of vertices using $|V| = O(\sqrt{n})$ nondeterministic steps and verify that they form a clique in polynomial time.</p>

<p>Some other languages $L$ of dense graphs in $\mathsf{NP}$ are also in $O(\sqrt{n})$-$\mathsf{PTIME}$.  This is the case for any problem where a subset of the vertices serves as a certificate, and the size of the input graph is $\Omega(|V|^2)$.  Examples are the promise versions of Induced Path or 3-Colouring for the case of dense graphs.  Other problems seem to require larger certificates, for instance a list of vertices defining a Hamiltonian circuit seems to require $\Omega(|V| \log |V|)$ bits.  It is not clear to me whether one could use an amount of nondeterminism that is too small to guess the certificate to decide such problems.</p>

<p>Given that $n^\varepsilon$-$\mathsf{P}$ can contain NP-complete languages, it then seems interesting to ask where in the bounded nondeterminism hierarchy potentially easier languages fall.  One might expect GI, as a language that does not seem to be NP-complete, to be in the hierarchy closer to $\log n$-$\mathsf{P}$ than to $n$-$\mathsf{P}$.  However, the obvious certificate for GI specifies the map using $|V|\log |V|$ bits, which is $\omega(\sqrt{n})$.</p>

<p>Another way to think about this question: is specifying a map between the sets of vertices a shortest possible certificate for GI?</p>

<p><em>Edit:</em> Some further (corrected) remarks follow, to address the comments of Joshua Grochow.</p>

<p>If a certificate uses $f(n) = \Omega(\log n)$ bits and can be checked in polynomial time, then brute force gives an algorithm for GI taking $poly(n)2^{O(f(n))} = 2^{O(f(n))}$ time.
With a certificate of size $O(\sqrt{n})$, brute force gives an algorithm taking $2^{O(\sqrt{n})}$ time,
while a certificate of size $O(\sqrt{n}\log n)$ yields a brute force approach taking $2^{O(\sqrt{n}\log n)}$ time.
The long-standing upper bound of Luks is $2^{O(\sqrt{n\log n})}$ time, which is between these two bounds up to constant exponents.</p>

<p>These considerations suggest that there might be an alternative approach to GI.
The approach of Luks seems to rely at its core on identifying a subset of generators of an associated group.
A nondeterministic machine might therefore guess a subset of the group.  These subsets could then be checked exhaustively to yield a deterministic algorithm.
If the list of elements can be specified succinctly, either because the associated group is never much larger than the size of the graph, or because the number of generators required is always small, and checking each candidate subset does not take too long, then this might yield an alternative approach to GI.</p>

<ul>
<li>Chandra M. R. Kintala and Patrick C. Fischer, <em>Refining Nondeterminism in Relativized Polynomial-Time Bounded Computation</em>, SIAM Journal on Computing <strong>9</strong>(1), 46–53, 1980.  doi:<a href="http://dx.doi.org/10.1137/0209003">10.1137/0209003</a></li>
<li>Judy Goldsmith, Matthew A. Levy, Martin Mundhenk, <em>Limited nondeterminism</em>, SIGACT News <strong>27</strong>(2), 20–29, 1996. doi:<a href="http://dx.doi.org/10.1145/235767.235769">10.1145/235767.235769</a></li>
<li>László Babai and Eugene M. Luks, <em>Canonical Labeling of Graphs</em>, STOC 1983, 171–183.  doi:<a href="http://dx.doi.org/10.1145/800061.808746">10.1145/800061.808746</a></li>
</ul>

CC BY-SA 3.0
2014-04-04T10:42:53.147Z
So, if the graph is given as adjacency matrix of size $n^2$ does that mean I can make a linear number of non-deterministic moves w.r.t to the vertex set size $n$?
John D.
CC BY-SA 3.0
2014-04-04T12:09:26.743Z
@user17410: Yes, the representation should not matter too much, as long as the size of any instance is $O(|V|^2)$.  (If they are unreasonably padded to have size $\Omega((|V|\log|V|)^2)$ then of course the square root bound is enough.)
András Salamon
CC BY-SA 3.0
2014-04-04T19:16:19.493Z
I think you may be asking for an algorithm better than the best known... If I understand, a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm would yield a $2^{O(\sqrt{n})}$ deterministic algorithm. The current best known deterministic algorithm takes time $2^{O(\sqrt{n} \log^2 n)}$.
Joshua Grochow
CC BY-SA 3.0
2014-04-10T04:06:27.937Z
@AndrásSalamon: Brute force = $n!poly(n) \approx 2^{O(n \log n)}$ NOT $2^{O(\sqrt{n} \log^2 n)}$... Also, I don't see why a certificate of size $\sqrt{n}$ leads to a brute force algorithm of time $2^{\sqrt{n} \log n}$ rather than $2^{O(\sqrt{n})}$ - can you elaborate? Maybe I am missing something in the definition of the "PTIME" notation?
Joshua Grochow
CC BY-SA 3.0
2014-04-10T19:10:56.363Z
@JoshuaGrochow: Thanks for your careful reading; I hope in the latest version I have managed to avoid too many mistakes.
András Salamon
CC BY-SA 3.0
2014-04-11T00:38:15.510Z
The space of relevant non-identity permutations is smaller than n!, http://oeis.org/A186202 to be exact.
Chad Brewbaker
CC BY-SA 3.0
2014-04-11T00:43:03.313Z
@Chad: that sounds interesting enough to turn into an answer?
András Salamon
CC BY-SA 3.0
2014-04-11T06:36:38.093Z
Just to be clear the number of vertices is $\Theta(\sqrt{n})$, right?
Thomas Steinke
CC BY-SA 3.0
2014-04-11T10:42:58.907Z
@Thomas: the question is interesting for both dense and sparse graphs, so I haven't specified.
András Salamon
CC BY-SA 3.0
2015-11-08T15:21:37.563Z
I think that Babai's quasi-polynomial time algorithm would lead to poly-logarithmic bounded nondeterministic algorithm.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-01-16T22:58:54.067Z
@MohammadAl-Turkistany: Maybe, but I'll have to think about it a bit. There are points in Babai's algorithm where, once the color-degree is below polylog it applies the bounded-deg GI test, as in the previous best algorithm, and it's not clear if one can either make the polylog deg GI test into polylog-bounded nondeterminism, or whether one can continue Babai's recursion further to get the degree down to, say, constant color-degree. If and when I figure that out I'll update my answer - if you have thoughts on this I'm happy to chat, but this is probably not the right place to work through it.
Joshua Grochow
<cc.complexity-theory><graph-theory><graph-isomorphism><nondeterminism>
Can graph isomorphism be decided with square root bounded nondeterminism?
András Salamon
# Can graph isomorphism be decided with square root bounded nondeterminism?

(Asked by: username_0 on 2014-04-04)

*Bounded nondeterminism* associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those languages that are accepted by some nondeterministic Turing machine $M$ obeying the same resource bounds as are used to define $C$, but where $M$ is allowed to make at most $g(n)$ nondeterministic moves. (I am using the notation of Goldsmith, Levy and Mundhenk, instead of the original by Kintala and Fischer, and $n$ is the size of the input.)

My question:

> Is there a constant $c\ge0$ such that GRAPH ISOMORPHISM is in $c\sqrt{n}$-$\mathsf{PTIME}$?

(*Edit:* Joshua Grochow pointed out that a positive answer to this question would imply an algorithm for GI that has better asymptotic runtime bounds than are currently known. I would therefore be happy to relax the bound, allowing $o(\sqrt{n}\log n)$ nondeterministic moves.)

---

## Background

For every fixed constant $c \ge 0$, $\mathsf{PTIME} = {c\log n}$-$\mathsf{PTIME}$, as $c\log n$ nondeterministic moves create at most a polynomial number of configurations to explore deterministically. Moreover $\mathsf{NP} = \cup\_c n^c\text{-}\mathsf{PTIME}$, and by means of padding one can exhibit NP-complete languages in $n^\varepsilon$-$\mathsf{P}$ for every $\varepsilon > 0$.

Kintala and Fischer observed that deciding if an input graph with vertices $V$ has a $(|V|/3)$-clique is $\mathsf{NP}$-complete, but is in $O(\sqrt{n})$-$\mathsf{PTIME}$. To see this, discard the vertices which have at most $|V|/3 - 2$ neighbours. If there are too few remaining vertices, then reject. Otherwise the remaining vertices form a graph of size $\Omega(|V|^2)$. Then guess a $|V|/3$-subset of vertices using $|V| = O(\sqrt{n})$ nondeterministic steps and verify that they form a clique in polynomial time.

Some other languages $L$ of dense graphs in $\mathsf{NP}$ are also in $O(\sqrt{n})$-$\mathsf{PTIME}$. This is the case for any problem where a subset of the vertices serves as a certificate, and the size of the input graph is $\Omega(|V|^2)$. Examples are the promise versions of Induced Path or 3-Colouring for the case of dense graphs. Other problems seem to require larger certificates, for instance a list of vertices defining a Hamiltonian circuit seems to require $\Omega(|V| \log |V|)$ bits. It is not clear to me whether one could use an amount of nondeterminism that is too small to guess the certificate to decide such problems.

Given that $n^\varepsilon$-$\mathsf{P}$ can contain NP-complete languages, it then seems interesting to ask where in the bounded nondeterminism hierarchy potentially easier languages fall. One might expect GI, as a language that does not seem to be NP-complete, to be in the hierarchy closer to $\log n$-$\mathsf{P}$ than to $n$-$\mathsf{P}$. However, the obvious certificate for GI specifies the map using $|V|\log |V|$ bits, which is $\omega(\sqrt{n})$.

Another way to think about this question: is specifying a map between the sets of vertices a shortest possible certificate for GI?

*Edit:* Some further (corrected) remarks follow, to address the comments of Joshua Grochow.

If a certificate uses $f(n) = \Omega(\log n)$ bits and can be checked in polynomial time, then brute force gives an algorithm for GI taking $poly(n)2^{O(f(n))} = 2^{O(f(n))}$ time.
With a certificate of size $O(\sqrt{n})$, brute force gives an algorithm taking $2^{O(\sqrt{n})}$ time,
while a certificate of size $O(\sqrt{n}\log n)$ yields a brute force approach taking $2^{O(\sqrt{n}\log n)}$ time.
The long-standing upper bound of Luks is $2^{O(\sqrt{n\log n})}$ time, which is between these two bounds up to constant exponents.

These considerations suggest that there might be an alternative approach to GI.
The approach of Luks seems to rely at its core on identifying a subset of generators of an associated group.
A nondeterministic machine might therefore guess a subset of the group. These subsets could then be checked exhaustively to yield a deterministic algorithm.
If the list of elements can be specified succinctly, either because the associated group is never much larger than the size of the graph, or because the number of generators required is always small, and checking each candidate subset does not take too long, then this might yield an alternative approach to GI.

* Chandra M. R. Kintala and Patrick C. Fischer, *Refining Nondeterminism in Relativized Polynomial-Time Bounded Computation*, SIAM Journal on Computing **9**(1), 46–53, 1980. doi:[10.1137/0209003](http://dx.doi.org/10.1137/0209003)
* Judy Goldsmith, Matthew A. Levy, Martin Mundhenk, *Limited nondeterminism*, SIGACT News **27**(2), 20–29, 1996. doi:[10.1145/235767.235769](http://dx.doi.org/10.1145/235767.235769)
* László Babai and Eugene M. Luks, *Canonical Labeling of Graphs*, STOC 1983, 171–183. doi:[10.1145/800061.808746](http://dx.doi.org/10.1145/800061.808746)

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism, nondeterminism
> **Comments:**
> **username_1**: So, if the graph is given as adjacency matrix of size $n^2$ does that mean I can make a linear number of non-deterministic moves w.r.t to the vertex set size $n$?  
> **username_0**: @user17410: Yes, the representation should not matter too much, as long as the size of any instance is $O(|V|^2)$.  (If they are unreasonably padded to have size $\Omega((|V|\log|V|)^2)$ then of course the square root bound is enough.)  
> **username_2**: I think you may be asking for an algorithm better than the best known... If I understand, a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm would yield a $2^{O(\sqrt{n})}$ deterministic algorithm. The current best known deterministic algorithm takes time $2^{O(\sqrt{n} \log^2 n)}$.  
> **username_2**: @AndrásSalamon: Brute force = $n!poly(n) \approx 2^{O(n \log n)}$ NOT $2^{O(\sqrt{n} \log^2 n)}$... Also, I don't see why a certificate of size $\sqrt{n}$ leads to a brute force algorithm of time $2^{\sqrt{n} \log n}$ rather than $2^{O(\sqrt{n})}$ - can you elaborate? Maybe I am missing something in the definition of the "PTIME" notation?  
> **username_0**: @JoshuaGrochow: Thanks for your careful reading; I hope in the latest version I have managed to avoid too many mistakes.  
> **username_3**: The space of relevant non-identity permutations is smaller than n!, http://oeis.org/A186202 to be exact.  
> **username_0**: @Chad: that sounds interesting enough to turn into an answer?  
> **username_4**: Just to be clear the number of vertices is $\Theta(\sqrt{n})$, right?  
> **username_0**: @Thomas: the question is interesting for both dense and sparse graphs, so I haven't specified.  
> **username_5**: I think that Babai's quasi-polynomial time algorithm would lead to poly-logarithmic bounded nondeterministic algorithm.  
> **username_2**: @MohammadAl-Turkistany: Maybe, but I'll have to think about it a bit. There are points in Babai's algorithm where, once the color-degree is below polylog it applies the bounded-deg GI test, as in the previous best algorithm, and it's not clear if one can either make the polylog deg GI test into polylog-bounded nondeterminism, or whether one can continue Babai's recursion further to get the degree down to, say, constant color-degree. If and when I figure that out I'll update my answer - if you have thoughts on this I'm happy to chat, but this is probably not the right place to work through it.  

---

## 1 answers

### Answer by username_2 on 2014-04-11. Score: 8 | Accepted answer

First, (as has now been edited into the question statement) a positive answer to your question would immediately improve the state of the art in worst-case bounds for graph isomorphism. For a $O(\sqrt{n})-\mathsf{PTIME}$ algorithm yields a $2^{O(\sqrt{n})}$-time deterministic algorithm, but the current best known for GI is only $2^{O(\sqrt{n \log n})}$

Second, it is not even immediately clear to me whether or not the current best algorithm is in fact a $O(\sqrt{n \log n})-\mathsf{PTIME}$ algorithm, although the first part of it clearly is, in some sense. The algorithm first guesses a set of vertices of size $\sqrt{n/\log n}$ to individualize (Zemlyachenko's trick - see [here](http://dx.doi.org/10.1007/3-540-10854-8_4) for an exposition in English), which can be done by guessing $\sqrt{n \log n}$ bits nondeterministically. However, after guessing those and individualizing (in deterministic poly time), it applies the best-known bounded-degree isomorphism test, which takes time $n^{O(d /\log d)}$ (Theorem 9.1 of [this paper](http://dx.doi.org/10.1109/SFCS.1983.10)), and applies it in the case of $d=O(\sqrt{n \log n})$. I'd have to think carefully about whether the latter algorithm could be turned into a $O(\sqrt{n \log n})-\mathsf{PTIME}$ algorithm (seems like an interesting question...)

> **Comments:**
> **username_3**: Do you have links to versions not behind a paywall? I have never seen an actual implementation of Zemlyachenko's trick or the bounded degree isomorphism test. Partitioning vertices by degree like NAUTY speeds things up, but those with the same degree you still have to check all prime cycle permutations on them AFIK.  
> **username_2**: @Chad: I'm unfortunately not aware of non-paywalled versions of those articles. However, Zemlyachenko's trick is quite simple to implement in practice and essentially reduces the degree. For practical implementation of Zemlyachenko's trick, i think the only question is the trade-off between enumerating sets of vertices to individualize (exponential in the size of the set) and any potential gains made by effectively reducing the degree. I do not know if it is actually implemented in NAUTY or other practical isomorphism algorithms.  
> **username_2**: @Chad: By the way, testing prime cycle permutations only suffices for detecting a nontrivial automorphism; it does not suffice for testing isomorphism. For example, if $G$ is a graph without nontrivial automorphisms, let $\pi$ be *any* permutation - not necessarily a prime cycle. Then $\pi(G)$ is isomorphic to $G$, and $\pi$ is the *only* isomorphism between $G$ and $\pi(G)$. But this isomorphism would not be detected by only considering prime cycles.  
> **username_3**: At the cost of doubling $n$, ISO can be computed with AUT by putting both graphs in an adjacency matrix.  
> **username_2**: @Chad: If you do that, then there are already $n!$ prime-cycle permutations of order 2, so you've lost any potential savings. This is related to the fact that the reduction you describe is from ISO to computing a *generating set* for the automorphism group. There is no known poly-time reduction from ISO to the problem of merely deciding whether a graph has a nontrivial automorphism.  
> **username_3**: NAUTY stands for No AUTomorphoisms Yes?  McKay is going about it the canonical form matching way.  
> **username_6**: @JoshuaGrochow Is $NTIME(n)$ same as $n-PTIME$ here?  
> **username_2**: @VS. I don't think so. For example, $n$-PTIME includes languages decidable by an algorithm which uses n nondeterministic bits and takes $O(n^2)$ time, but $\mathsf{NTIME}(n)$ (probably) does not include all such languages.  
> **username_7**: @JoshuaGrochow What is the complement of $\beta P$ (should be $\beta$ conondeterministic bits and in $P$) and is it identical to $\beta' P$ at a relation between $\beta$ and $\beta'$?  
> **username_2**: The complement is as you say, and I don't understand the second part of your question.  
> **username_7**: @JoshuaGrochow I think $\beta$ and $\beta'$ are exponentially related in $\overline{\beta P}\subseteq \beta'P$ if $\beta=\Omega(n)$ if $coNP\not\subseteq NP$ but if $\beta=o(n)$ it is unclear.  
> **username_2**: I don't think anything better than exponential is known. You should be able to relate it to standard classes like coNP using padding, but I'd have to think about it a bit.  

---

