Liniowe równanie diofantyny w liczbach całkowitych nieujemnych

Jest tylko bardzo mało informacji na temat kompletnego NP rozwiązania problemu liniowego równania diofantyny w liczbach całkowitych nieujemnych. To znaczy, czy jest to rozwiązanie w nieujemne $x_1,x_2, ... , x_n$ do równania , gdzie wszystkie stałe są dodatnie? Jedyną godną uwagi wzmianką o tym problemie, który znam, jest Teoria programowania liniowego i liczb całkowitych Schrijvera . I nawet wtedy jest to raczej krótka dyskusja. $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$

Byłbym bardzo wdzięczny za wszelkie informacje lub referencje, które możesz podać na temat tego problemu.

Są dwa pytania, na których najbardziej mi zależy:

Czy jest silnie NP-Complete?
Czy związany z tym problem zliczania liczby rozwiązań # P-trudny, czy nawet # P-kompletny?

cc.complexity-theory reference-request np-hardness counting-complexity 4evergr8ful
źródło

To naprawdę nie jest pytanie na poziomie badawczym i trudno mi uwierzyć, że nie znalazłeś więcej informacji. Zacznij tutaj: en.wikipedia.org/wiki/Knapsack_problem

domotorp

dla 2), afaik nie ma znanego przykładu problemu NP-zupełnego, którego wersja z liczeniem naturalnym nie jest # P-pełna. znalezienie oszczędnego ograniczenia dla konkretnego problemu może być łatwiejsze niż znalezienie odniesienia. ten artykuł robi to dla ściśle powiązanego #SubsetSum: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf

Sasho Nikolov

Czy mogę prosić zarówno @domotorp, jak i 4evergr8ful o nieco więcej uprzejmości? Pierwszy mógł wyjaśnić, w jaki sposób problem plecakowy sprowadza się do takich równań diofantycznych, co wydaje się, że tak jest, podczas gdy 4evergr8ful mógł być może ochłonąć, zwłaszcza, że zarówno prosi o pomoc, jak i oczywiście nie ma doświadczenia w działaniu tego forum . Ale myślałem również o problemie plecaka i wcale nie jest dla mnie jasne, czy sprowadza się on do pozytywnych rozwiązań równań diofantycznych.

Andrej Bauer,

OP, jak wspomniano @Austin, ten sam pomysł programu dynamicznego, co w przypadku plecaka, rozwiązuje problem w czasie wielomianowym, gdy

są ograniczone wielomianem. więc nie, problem nie jest silnie np. kompletny. a domotorp miał dobry powód, aby skierować Cię na stronę wiki plecaka.

a_{i}

$a_i$

Sasho Nikolov

@ 4evergr8ful Pewnie, założyłem, że sparafrazowałeś cytat. To dobrze. Jednak źle je zacytowałeś, zmieniając „sześć” na „każdy”. Ponieważ G&J definiuje jako oszczędne (tzn. Liczba rozwiązań jest dokładnie taka sama), NIE jest prawdą, że każde zmniejszenie między problemami w NP może być zmniejszone, JEŻELI P = Parzystość-P. Powodem tego jest to, że standardowa redukcja z SAT do NAE-SAT wprowadza czynnik, który jest potęgą 2. Jest to oczekiwane, ponieważ SAT jest kompletny dla Parzystości-P, ale NAE-SAT jest łatwy (istnieje oczywista para przypisania, więc odpowiedź jest zawsze parzysta = 0).

Tyson Williams

Odpowiedzi:

Jeśli chodzi o (1), problem nie jest silnie trudny do NP, por. Wniosek 1 tutaj :

Papadimitriou, CH (1981). O złożoności programowania liczb całkowitych. Journal of the ACM , 28 (4), 765-768.

Jeśli chodzi o (2), problem oczywiście polega na #P, jeśli wszystkie stałe są dodatnie. Istnieje również wersja SubsetSum z pełną wersją P, która prawie pasuje do Twojego wystąpienia problemu, ale wymaga jednak, aby wynosił 0 lub 1, patrz tutaj : $x_i$

Faliszewski, P. i Hemaspaandra, L. (2009). Złożoność porównania indeksu mocy. Informatyka teoretyczna 410 (1), 101–107.

$x_i\in \{0,1\}$

Christoph Haase
źródło

W ogóle nie jestem ekspertem w tej dziedzinie, ale chciałbym rozpocząć konstruktywną dyskusję. Oto próba oparta na pytaniu math.stackexchange.com Policz liczbę pozytywnych rozwiązań dla liniowego równania diofantycznego . Te rzeczy są związane z wielomianami Erharta, o których nic nie wiem, i myślę też o komentarzach @ SashoNikolov powyżej.

$N(a_1, a_2, \ldots, a_n; b)$

a_{n} x_{n} + a_{n - 1} x_{n - 1} + \dots + a_{1} x_{1} = b,

$a_n x_n + a_{n-1} x_{n-1} + \cdots + a_1 x_1 = b,$

a_{i}

$a_i$

b

$b$

N (a_{1}; b) = {\begin{cases} 1 & if a_{1} ∣ b \\ 0 & otherwise \end{cases}

$N(a_1; b) = \begin{cases} 1 & \text{if $a_1 \mid b$} \\\\ 0 & \text{otherwise} \end{cases}$

N (a_{1}, \dots, a_{n + 1}; b) = \sum_{0 \leq k \leq b / a_{n + 1}} N (a_{1}, \dots, a_{n}; b - a_{n + 1} k)

$N(a_1, \ldots, a_{n+1}; b) = \sum_{0 \leq \ k \ \leq b/a_{n+1}} N(a_1, \ldots, a_n; b - a_{n+1} k)$

k

$k$

b

$b$

Andrej Bauer
źródło

Drogi Andrej, w przypadku dużej twardości NP mierzymy wartość wkładu, a nie jego długość. Zobacz także: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

domotorp

@domotorp, myślę, że Andrej zajmuje się drugim pytaniem, o # kompletności P, a nie pierwszym o silnej NP-kompletności, na którą, jak widzę, bardzo łatwo jest odpowiedzieć (nie, problemem nie jest silnie NP -kompletny). Andrej, jestem zdezorientowany, co chcesz tu pokazać? Ponieważ problem decyzyjny jest NP-kompletny, nie można liczyć na liczbę rozwiązań. Czy masz nadzieję na przybliżenie liczby rozwiązań? A może masz algorytm czasu szybciej niż wykładniczy?

Sasho Nikolov

BTW, myślę, że jest prawdopodobne, że algorytm w tym artykule (w przybliżeniu zliczający liczbę rozwiązań plecaka za pomocą programowania dynamicznego) można dostosować do problemu równania diofantycznego: cs.utexas.edu/~klivans/focs11.pdf

Sasho Nikolov

Dowiedziałem się jeszcze jednego faktu na temat tego problemu. Istnieją trzy rodzaje ludzi: ci, którzy nazywają to #liniowym problemem diofantynowym, ci, którzy nazywają to #niezwiązanym problemem plecakowym, i wreszcie ci, którzy nazywają to problemem denumeracyjnym. I nie wydają się ze sobą rozmawiać.

4evergr8ful