Комментарии 3
Ох это слишком сложная и интересная тема для короткого обзора. Хотел добавить.
Между P < NP < Pspace куча классов. И строго не доказано, что они вообще все не равны. Есть возможность коллапса этой иерархии.
А еще важна time hirarchy theorem, которая немного похожа на теорему Геделя (используется диагонализация). Она позволяет всегда конструировать искусственные задачи сложнее заданного класса. Но они все непрактичные.
Вся соль NP проблемы, что в этом классе оказалась куча практических проблем. И никто не знает почему. Почти все прикладное сложнее P сидит в NP.
Как-то так. Поправьте если что.
где бы посмотреть этот Travelling Salesman (Коммивояжёр, 2012)?
Что-то я подозреваю, что задачу со сложностью TOWER сложно найти. Конечно можно что-то придумать что-то про раскраску графа типа как в задаче про число Грэмма.
Есть проблемы гораздо сложнее, чем NP-Complete