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

Когда дело доходит до сложных задач, специалисты по информатике часто заходят в тупик. Рассмотрим, например, известную задачу о поиске кратчайшего маршрута туда и обратно, проходящего через каждый город на карте ровно один раз. Все известные методы решения этой «задачи коммивояжёра» работают очень медленно на картах с большим количеством городов, и исследователи подозревают, что не существует способа их оптимизировать. Но никто не знает, как это доказать.

Более 50 лет исследователи в области теории вычислительной сложности пытаются превратить интуитивные утверждения, такие как «задача коммивояжёра сложна», в железобетонные математические теоремы, но без особого успеха. Всё чаще они также ищут строгие ответы на связанный с этим и более туманный вопрос: почему их доказательства не увенчались успехом?

Читать далее