Для частных случаев задачи о коммивояжёре известны полиномиальные приближённые алгоритмы. В предположении P!=NP для общей задачи о коммивояжёре такие алгоритмы не существуют. При необходимости решить задачу с некоторой константной точностью, то мы вынуждены использовать точные алгоритмы. Задача о коммивояжёре может быть решена точно за время 2^n с использованием экспоненциальной памяти или за время 4^n с полиномиальной памятью. Открытым вопросом является существование алгоритма с временем работы 2^n и лишь полиномиальной памятью. В докладе мы разберём частичный ответ на этот вопрос: за 2^n шагов с использованием лишь полиномиальной памяти может быть найдено любое константное приближение задачи о коммивояжёре. Также мы поговорим о точных и приближённых алгоритмах решения задачи о кратчайшей надстроке.