Jakie istnieją algorytmy rozwiązywania układów liniowych z liczbami naturalnymi?

Patrzę na następujący problem:

Biorąc pod uwagę wymiarowe wektory liczb naturalnych i niektóre wektory wejściowe , czy jest liniową kombinacją z współczynnikami liczb naturalnych?$n$$v_1, \ldots, v_m$$u$$u$$v_i$

tzn. czy są jakieś gdzie ?$t_1, \ldots, t_m \in \mathbb{N}$$u = t_1 v_1 + \dots + t_m v_m$

Oczywiście rzeczywistą wersję tego problemu można rozwiązać za pomocą eliminacji Gaussa. Zastanawiam się, czy zbadano całkowitą wersję tego problemu? Jakie algorytmy istnieją, aby go rozwiązać?

Zauważ, że używa to liczb naturalnych, ale nie modułowej arytmetyki, więc jest to nieco odrębne od chińskiego twierdzenia o pozostałych elementach i podobnych systemach. Wydaje się również, że jest to związane z równaniami diofantycznymi, ale zastanawiam się, co zrobiono w przypadku, gdy uwzględniane są tylko nieujemne liczby całkowite? Przypomina to również problem wielowymiarowej sumy częściowej, uogólnionej, abyśmy mogli pobrać dowolną liczbę kopii każdego wektora. Wydaje się to również związane z testowaniem, czy jest elementem sieci generowanej przez , z tym wyjątkiem, że tutaj dopuszczamy tylko kombinacje liniowe z nieujemnymi współczynnikami.$u$$v_1,\dots,v_m$

Dla każdego zainteresowanego jest to motywowane przez sprawdzenie, czy wektor Parikha jest w zestawie liniowym, jak w twierdzeniu Parikha .

W szczególności interesuje mnie algorytm, który mógłby rozwiązać problem za pomocą operacji na liczbach naturalnych, unikając wchodzenia w liczby rzeczywiste / zmiennoprzecinkowe.

Twój problem jest NP-zupełny, poprzez redukcję z sumy podzbioru (dotyczy NP, ponieważ fakt, że wszystko jest nieujemne, wystarczająco dobrze ogranicza współczynniki rozwiązania). Biorąc pod uwagę instancję z podzbioru Suma (czy istnieje podzbiór sumujący się do ?), instancję twojego problem w następujący sposób. Dla każdego , stawiamy jako wektor z dwoma niezerowymi wpisami: oraz oraz być wektorem z unikalnym niezerowym wpisem . Wektorem docelowym jest$S = \{s_1,\ldots,s_n\}, T$$S$$T$$v_1,\ldots,v_{2n},u$$1 \leq i \leq n$$v_i$$v_{i,i} = 1$$v_{i,n+1} = s_i$$v_{n+i}$$v_{n+i,i} = 1$$u=1,\ldots,1,T$. Każda naturalna kombinacja równa musi wybrać dokładnie jeden z każdego z , a zatem koduje podzbiór którego suma jest równa wartość ostatniego składnika.$v_1,\ldots,v_{2n}$$1,\ldots,1,\ast$$v_i,v_{n+i}$$S$