¿Qué algoritmos existen para resolver sistemas lineales de números naturales?

Estoy mirando el siguiente problema:

Dados vectores dimensionales de números naturales v 1 , ... , v my algún vector de entrada u , ¿es u una combinación lineal de v i 's con coeficientes numéricos naturales?$n$$v_1, \ldots, v_m$$u$$u$$v_i$

es decir, ¿hay alguna donde u = t 1 v 1 + ⋯ + t m v m ?$t_1, \ldots, t_m \in \mathbb{N}$$u = t_1 v_1 + \dots + t_m v_m$

Obviamente, la versión en números reales de este problema se puede resolver utilizando la eliminación gaussiana. Me pregunto, ¿se ha estudiado la versión entera de este problema? ¿Qué algoritmos existen para resolverlo?

Tenga en cuenta que esto está usando números naturales, pero no aritmética modular, por lo que está algo separado del Teorema del resto chino y sistemas como ese. Además, parece estar relacionado con las ecuaciones de diofantina, pero me pregunto qué se ha hecho en el caso en que solo se consideran enteros no negativos. Esto también recuerda un problema de suma de subconjuntos multidimensional, generalizado para permitirnos tomar un número arbitrario de copias de cada vector. También parece estar relacionado con probar si es un elemento de la red generada por v 1 , ... , v m , excepto que aquí solo permitimos combinaciones lineales con coeficientes no negativos.$u$$v_1,\dots,v_m$

Para cualquier persona interesada, esto se motiva al observar si un vector Parikh está en un conjunto lineal, como en el Teorema de Parikh .

En particular, estoy interesado en un algoritmo que pueda resolver el problema utilizando solo operaciones de números naturales, evitando entrar en los números reales / flotantes.

Su problema es NP completo, mediante la reducción de Subset Sum (está en NP ya que el hecho de que todo sea no negativo limita suficientemente los coeficientes de la solución). Dada una instancia de Subset Sum (¿hay un subconjunto de S sumando a T ?), Construimos una instancia v 1 , ... , v 2 n , u de su problema como sigue. Para cada 1 ≤ i ≤ n , ponemos v $S = \{s_1,\ldots,s_n\}, T$$S$$T$$v_1,\ldots,v_{2n},u$$1 \leq i \leq n$$v_i$ser el vector con dos entradas distintas de cero: y v i , n + 1 = s i , y v n + i ser el vector con una única entrada distinta de cero v n + i , i = 1 . El vector objetivo es u = 1 , ... , 1 , T . Cada combinación natural de v 1 , ... , v 2 $v_{i,i} = 1$$v_{i,n+1} = s_i$$v_{n+i}$$v_{n+i,i} = 1$$u=1,\ldots,1,T$$v_1,\ldots,v_{2n}$igual a debe seleccionar exactamente uno de cada uno de v i , v n + i , y así codifica un subconjunto de S cuya suma es el valor del último componente.$1,\ldots,1,\ast$$v_i,v_{n+i}$$S$