Beyond average case complexity, which is discussed below, there is also a rich research line on approximation algorithms. Interestingly, the effectiveness of ap

Beyond average case complexity, which is discussed below, there is also a rich research line on approximation algorithms. Interestingly, the effectiveness of approximation algorithms is not uniform across NP-Complete problems. There are problems where efficient approximation algorithms can be arbitrarily good and there are problems where if P!=NP then approximation algorithms have hard caps on their effectiveness. This is relevant for a lot of optimization tasks where you don't necessarily care about getting the best possible solution but would be happy getting pretty close.