Реверсивная математика демонстрирует, почему сложные задачи сложны

[antiquar]

интуитивные утверждения, такие как «задача коммивояжёра сложна»

Почему "интуитивные"? Вполне конкретное: коммивояжер NP-полна, соответственно, любая NP полиномиально сводится коммивояжеру.

[D7ILeucoH]

По поводу эквивалентности теорий я кричу давно. Когда в школе началась физика, я орал от того что три закона Ньютона буквально говорят об одном и том же.

Надо ли доказывать что-то?

А в университете меня заставляли придумывать оптимальный алгоритм для решения задачи коммивояжёра, только вот я чёто не знал что она так называется и что у неё нет решения. Как решать не понял, пришлось взять решение друга по похожей задаче и сильно изменить алгоритм.

Для оптимизации часто нужно посмотреть вообще в другую сторону, именно там скрываются реальные открытия.

[IgorIlyin]

Всё биты строки - это верхняя граница сложности, если мы говорим о том же, о чем говорил Колмогоров. Вместо всей строки можно послать программу её генерации, что по размеру волне может быть меньше.

[AndrewN]

Так имеется ввиду же общий случай. Вы можете доказать, что для любой строки возможно написать программу не генерации, которая будет короче эту строки?

[Deosis]

Битовых строк длины n - 2^n, битовых строк меньшей длины - 2^n - 1

Поэтому найдется несжимаемая строка.