ВСЕ СТАТЬИ
•
habr.com•наука
[Перевод] Реверсивная математика демонстрирует, почему сложные задачи сложны. Когда дело доходит до сложных задач, специалисты по информатике часто заходят в тупик. Рассмотрим, например, известную задачу о поиске кратчайшего маршрута туда и обратно, проходящего через каждый город на карте ровно один раз. Все известные методы решения этой «задачи коммивояжёра» работают очень медленно на картах с большим количеством городов, и исследователи подозревают, что не существует способа их оптимизировать. Но никто не знает, как это доказать. Более 50 лет исследователи в области тео...