Какие существуют алгоритмы для решения линейных систем с натуральными числами?

9

Я смотрю на следующую проблему:

Для заданных мерных векторов натуральных чисел v 1 , , v m и некоторого входного вектора u , является ли u линейной комбинацией v i с коэффициентами натуральных чисел?nv1,,vmuuvi

т.е. есть ли где u = t 1 v 1 + + t m v m ?t1,,tmNu=t1v1++tmvm

Очевидно, что реальная версия этой проблемы может быть решена с использованием исключения Гаусса. Мне интересно, была ли изучена целочисленная версия этой проблемы? Какие существуют алгоритмы для его решения?

Обратите внимание, что здесь используются натуральные числа, но не модульная арифметика, поэтому она несколько отличается от китайской теоремы об остатках и подобных систем. Кроме того, похоже, что это связано с диофантовыми уравнениями, но мне интересно, что было сделано в случае, когда рассматриваются только неотрицательные целые числа? Это также напоминает многомерную задачу о сумме подмножеств, обобщенную для того, чтобы мы могли взять произвольное количество копий каждого вектора. Кажется также, что это связано с проверкой, является ли элементом решетки, порожденным v 1 , , v m , за исключением того, что здесь мы допускаем только линейные комбинации с неотрицательными коэффициентами.uv1,,vm

Для всех, кто заинтересован, это мотивируется тем, что вектор Париха находится в линейном множестве, как в теореме Париха .

В частности, я заинтересован в алгоритме, который мог бы решить проблему, используя только операции с натуральными числами, избегая углубления в вещественные числа / числа с плавающей запятой.

jmite
источник
2
Да, целочисленная версия (и различные кольцевые теоретические версии) были изучены. Целочисленная версия может быть решена путем исключения Гаусса. Версия с натуральным числом - это другой зверь. Мне кажется, что он должен быть NP-завершенным.
Томас Климпел
Как она может быть NP-полной, если она решена с помощью исключения Гаусса? Я до сих пор интересуюсь алгоритмами для него, даже если это проблема, которую можно решить.
Jmite
Также обратите внимание, что в проблеме, которую я рассматриваю, система может быть недоопределена, т. Е. . Не уверен, как это меняет это. m<n
jmite

Ответы:

9

S={s1,,sn},TSTv1,,v2n,u1invivi,i=1vi,n+1=sivn+ivn+i,i=1u=1,,1,Tv1,,v2n1,,1,vi,vn+iS

Юваль Фильмус
источник
Интересно. Вы придумали это доказательство или у меня есть ссылка на него, которую я мог бы привести? В любом случае, спасибо!
Jmite
1
@jmite Я только что придумал доказательства, хотя не могу исключить, что видел их.
Юваль Фильмус