Skip to main content
MathOverflow

Return to Question

+ top level tag (co.)
Source Link
Myshkin
Myshkin
  • 17.6k
  • 5
  • 71
  • 137

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

lastLast year Laslo Babai proved that the GI problem can be solved in (deterministic) time $\exp(log^c(n))$$\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?

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

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

Source Link
Arthur Kexu-Wang
Arthur Kexu-Wang
  • 193
  • 6

Is the Graph Isomorphism problem in βP class?

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