Isomorphism testing of projective planes can be done in $n^{O(\log \log n)}$. This class is contained in quasi-polynomial time. I would like to know more about this class and natural problems in it.

Is there a standard name for this class of problems?

Also, I am looking for a reference (or survey) that gives other natural problems (without known polynomial-time algorithms) in this class.

  • $\begingroup$ You mentioned sub-exponential time but not quasi-polynomial time, so I figured I'd mention the latter. ​ ​ $\endgroup$ – user12859 May 19 '16 at 12:44
  • $\begingroup$ @RickyDemer Yes. I will edit it. $\endgroup$ – Mohammad Al-Turkistany May 19 '16 at 12:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.