Существуют ли какие-либо недавние (не стесняйтесь добавлять и "старые") проблемы, которые воспринимались как NP, а потом кто-то придумал решение, которое является полиномиальным?Я думаю, что изучение этих случаев поможет развить умение решать критические проблемы наряду с практикой конкурентного программирования.