An *optimal meta algorithm* for a class C of computational problems is an algorithm A that can solve any problem P in C in some time T_P(n) and such that there does not exist an algorithm that can solve P significantly faster. A natural optimal algorithm for a class C in some sense provides the most satisfactory explanation to what makes certain problems in C hard and other problems easy.

 

In this high level and informal talk I will discuss for what classes of problems we might hope to get natural optimal algorithms, the works on the Sum-of-Squares SDP as a candidate optimal algorithm, and how such optimal algorithms/proof systems give rise to a computational analog of Bayesian probability.