3
$\begingroup$

βP is the limited nondeterminism NP, cf. https://complexityzoo.uwaterloo.ca/Complexity_Zoo:B#betap

Last year Laslo Babai proved that the GI problem can be solved in (deterministic) time $\exp(\log^c(n))$. In the introduction he said the branching factor in his algorithm was quasipolynomial bounded.

So if we use the algorithm on a nondeterministic Turing machine, can we say that GI is in βP?

$\endgroup$

0

You must log in to answer this question.