Псевдополиномиальный алгоритм с геометрической оптимизацией

 Рассмотрим систему линейных уравнений:
(1000α11α12α1m0100α21α22α2m0010αj1αj2αjm0001αn1αn2αnm)(x1x2xnxn+1xn+2xn+m)=0.
Она задает в пространстве Rn+m подпространство размерности m. В силу сказанного выше, все диофантовы приближения должны лежать в окрестности этого подпространства. Базисом этого пространства, как несложно убедиться, являются решения систем уравнений
(1000010000100001)(x1xnxn+1xn+m)=(αi1αinδi1δim).
или же
e(x1(i)x2(i)xs(i))=(αi1αinδi1δim)
Тем самым мы получили новый алгоритм:
Алгоритм 3.
Оценим сложность полученного алгоритма. На перебор коэффициентов теперь требуется порядка (2K)m3m+n операций (так как точек соседних с данной ровно 3m+n1 ). В итоге для нахождения первых I приближений требуется не более (2K)m3m+n(m+n+1)!Im+n+1 операций (то есть O((2K)mIm+n) при фиксированной размерности задачи).