Many problems have notoriously resisted the discovery of efficient (polynomial time) algorithms. Yet at the same time, we are unable to prove that any algorithm solving a fixed problem requires a certain amount of time (i.e. proving a lower bound). In fact, there exist results stating that a proof of a lower bound cannot rely exclusively on certain ideas.

To summarize, we are unable to find a fast algorithm, nor prove that one does not exist, and we even know which previous ideas are not clever enough to prove that one does not exist. We survey some of these results, and if time permits, introduce a possible way of getting around "the barriers" to proving a lower bound.