С beltway проблемой студенты знакомятся, проходя курсы биоинформатики, в частности, один из наиболее качественных и наиболее близкий по духу для программистов — курс Bioinformatics (Павла Певзнера) на coursera от University of California San Diego. Проблема привлекает внимание простотой постановки, практической важностью, ну и тем, что она до сих пор считается нерешенной при кажущейся возможностью решить ее простым кодированием. Проблема ставится таким образом. Возможно ли в полиномиальное время восстановить координаты множества точек $inline$X$inline$, если известно множество всех парных расстояний между ними $inline$Delta X$inline$?
Эта с виду простая задача до сих пор находится в списке нерешенных проблем вычислительной геометрии. Причем ситуация даже не касается точек в многомерных пространствах, тем более искривленных, проблемой является уже самый простой вариант — когда все точки имеют целочисленные координаты и локализованы на одной линии.
Читать полностью »