7
$\begingroup$

In a paper by Raphael Pass, he writes (page 162):

... most natural problems that we believe are hard on average for polynomial time are also believed hard for quasi-polynomial time.

In another post by Turkistany, he mentioned that the log-CLIQUE problem is solvable in quasi-polynomial time.

What are some other natural problems which we believe are hard on average for polynomial time, but can be decided/solved in quasi-polynomial time?

$\endgroup$

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.