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

 Пусть s=m+n. Допустим, мы знаем первые i совместных приближений. Переберем все s-элементные подмножества, вышеуказанного множества. Среди них обязательно найдется хотя бы один «базисный»   набор. Для каждого подмножества (p(t1),q(t1)), ,(p(ts),q(ts)), будем искать новое наилучшее приближение в виде
(p(новое),q(новое))=1jsaj(p(tj),q(tj))
Среди всех найденных таким образом «наилучших приближений» выберем минимальное, оно и будет искомым. Единственный вопрос, который остается открытым: в каких пределах перебирать коэффициенты a1,,as? Мы предлагаем выбирать эти коэффициенты в пределах K<aj<K, где K – некоторое целое, достаточно большое, положительное число. Если это число маленькое, то есть вероятность не найти новое наилучшее приближение (когда новое приближение много больше предыдущих). Чем число больше, тем более вероятно, что мы получим искомое приближение, но при этом сильно падает быстродействие алгоритма. На практике, мы постепенно увеличивали значение K, до тех пока эти изменения, приводили к изменению результирующей последовательности векторов наилучших приближений. Покажем корректность алгоритма. В виду ограниченности значения нового приближения ограничены и коэффициенты в разложении по базису. Следовательно, существует значение коэффициента K при котором алгоритм найдет все верные совместные приближения.
Алгоритм 2.
На перебор коэффициентов требуется порядка Km+n операций на каждом наборе (p(t1),q(t1))t1,,(p(ts),q(ts))tm+n. Таких наборов CI+m+nm+n. При большом I эта величина стремится к Im+n(m+n)!. В итоге для нахождения первых I приближений требуется порядка (2K)m+n(m+n+1)!Im+n+1 операций. Значит этот алгоритм полиномиальный относительно основного параметра I – количества приближений. В тоже время, для произвольных входных чисел, он не сможет достичь оценки O(Im+n+1), ввиду зависимости от параметра K.