For my work I'm looking for good examples of problems that are very compute-intensive and at the same having good and fast approximated solutions. Could you give me some examples?
I'm unsure if this question is right here. If not, just let me know and I will delete this.
One such example is the prime-counting function $\pi$. It is computationally hard to compute $\pi(x)$ for a large number $x$. However, it is known since 1962 that$$x\geqslant17\implies\frac x{\log x}<\pi(x)<\frac{30\log113}{113}\times\frac x{\log x}.$$