Just out of curiosity, What problems are believed to have an efficient algorithm, yet haven't been found such an algorithm for them?
This question came up to my mind after reading about PRIMES problem.
I hope this question is appropriate for this forum
Thanks!
I'll cover problems that are easy to solve (i.e. in $P$) and problems whose solutions are easy to verify (i.e. in $NP$), and some problems that are probably not, and try to explain why people think one way or the other.
Under standard complexity-theoretic assumptions, $P=BPP$, meaning that most randomized algorithms can be "derandomized" (this family of conjectures is called the derandomization hypotheses). You read about a specific example, PRIMES, and it is expected that that is an instance of a more general phenomenon. So for example, polynomial identity testing probably has a polynomial-time algorithm.
For similar reasons, it is conjectured that $NP=MA=AM$. See the Complexity Zoo for definitions of these classes). One language in $AM$ is graph non-isomorphism: the language of all pairs of graphs that are not isomorphic. Clearly its complement it in $NP$ (because you can check whether a purpurted permutation is in fact an isomorphism), so surprisingly the fact that two graphs are not isomorphic is something that is expected to be easy to verify given some proof. Yet (afaik) we do not know which $BPP$-language we have to derandomize to obtain this result. If $NP=MA$ or $P=RP$, then it is easy to verify that an arithmetic circuit is not minimal.
These sets, $BPP$ and $AM$ are (afaik) the "largest" classes of problems that are expected to collapse to $P$ and $NP$ respectively, meaning they are expected to be easy to solve, respectively, to verify.
So we do not know how to verify non-isomorphism yet, much less decide it (as in, solve it in $P$). Is it hard? Is it easy? Interestingly, if Graph isomorphism is so hard that it's NP Complete, then a widely believed complexity-theoretic hypothesis (that "the polynomial hierarchy is infinite") fails, so graph isomorphism is probably not NP-Complete. We do not know of any hypothesis that fails under the assumption that graph isorphism is easy, i.e. in $P$ or in $BPP$. The same goes for factoring: probably not NP-Complete, not known to be easy.*
Problems in this Wikipedia list of NP-Intermediate problems are not expected to be in $P$.
Linear programming has a polynomial algorithm if you only count the number of arithmetic operations ($+,-,\times$ etc). However, those arithmetic operations may involve numbers that are more than polynomially long, so the algorithm is called weakly polynomial. It is expected that there is an algorithm that doesn't suffer from this, called a strongly polynomial algorithm. For example, Mihály and Vempala [1] recently presented a plausible-looking candidate for such an algorithm.
*Scott Aaronson once quiped that factoring might as well be in $P$. It would collapse the world economy, sure, but it wouldn't collapse the polynomial hierarchy, so wouldn't be that impressive.
[1] Bárász, Mihály, and Santosh Vempala. "A new approach to strongly polynomial linear programming." (2010).
