Abstract
When dealing with computational problems, we always try to find efficient algorithms that solve them, for all possible instances. The concept of efficiency of an algorithm usually refers to its time complexity being polynomial on the input size. However, there are many relevant problems for which there is no hope that we will find efficient algorithms that find optimal solutions for all i…