Many natural computational problems occurring in practice are intractable, meaning that no efficient algorithms exist resolving
such problems. From a theoretical perspective the most intriguing case occurs with the family of NP-complete problems.
Despite extensive research, neither is an efficient algorithm known, nor has the existence of one been rigorously ruled out for any of such problems. While the common believe is that NP-complete problems are intractable, this does not eliminate the necessity of handling such problems in practice. For the last 50 years several ways have been developed to understand and cope with intractability, each of the ways having its own advantages and drawbacks.
In this talk we give an overview of several approaches to deal with hard computational problems developing in the Algorithmic methods laboratory at the St. Petersburg Department of Steklov Mathematical Institute.