Zmniejszyłem mój problem (algorytm układu tabeli) do następującego problemu:

Wyobraź sobie, że mam N zmiennych X1, X2, ..., XN. Mam także (nieokreśloną) liczbę nierówności, takich jak:

X1 > = 2
x2 + X3 > = 13
itp.

Każda nierówność jest sumą jednej lub więcej zmiennych i zawsze jest porównywana do stałej za pomocą operatora> =. Nie mogę z góry powiedzieć, ile nierówności będę miał za każdym razem, ale wszystkie zmienne muszą być nieujemne, więc to już jedna dla każdej zmiennej.

Jak rozwiązać ten system w taki sposób, aby wartości zmiennych były jak najmniejsze?

Dodany: Przeczytaj artykuł wikipedii i zdałem sobie sprawę, że zapomniałem wspomnieć, że zmienne muszą być liczbami całkowitymi. Zgadnij, że to czyni go NP-trudnym?