Линейное диофантово уравнение в неотрицательных целых числах

Существует очень мало информации, которую я могу найти по NP-полной задаче решения линейного диофантового уравнения в неотрицательных целых числах. То есть, есть решение в неотрицательном к уравнению , где все константы положительны? Единственное заслуживающее упоминания упоминание об этой проблеме, о которой я знаю, - в книге Шрайвера. $x_1,x_2, ... , x_n$ $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$ Теория линейного и целочисленного программирования . И даже тогда это довольно лаконичное обсуждение.

Поэтому я был бы очень признателен за любую информацию или ссылку, которую вы могли бы предоставить по этой проблеме.

Есть два вопроса, которые меня больше всего волнуют:

Это сильно NP-Complete?
Связанная проблема подсчета количества решений # P-hard или даже # P-complete?

cc.complexity-theory reference-request np-hardness counting-complexity 4evergr8ful
источник

Это действительно не вопрос исследовательского уровня, и мне трудно поверить, что вы не нашли больше информации. Начните здесь: en.wikipedia.org/wiki/Knapsack_problem

domotorp

для 2) afaik не существует известного примера NP-полной задачи, чья версия с естественным счетом не # P-полная. выяснить экономное сокращение вашей конкретной проблемы может быть проще, чем найти ссылку. эта статья делает это для тесно связанного #SubsetSum: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf

Сашо Николов

Могу ли я спросить у @domotorp и 4evergr8ful немного вежливости? Первый мог бы объяснить, как проблема ранца сводится к таким диофантовым уравнениям, что, как он, кажется, считает, имеет место, в то время как 4evergrful может, возможно, остыть, тем более что он одновременно просит помощи и явно неопытен в работе этого форума , Но я думал и о проблеме ранца, и мне совершенно не ясно, что она сводится к положительным решениям диофантовых уравнений.

Андрей Бауэр

OP, как упомянул @Austin, та же идея динамической программы, что и для ранца, решает вашу проблему за полиномиальное время, когда

ограничены полиномами. так что нет, проблема не сильно np-полная. и у domotorp была веская причина указать вам на страницу вики о рюкзаке.

a_{i}

$a_i$

Сашо Николов

@ 4evergr8ful Конечно, я предположил, что вы перефразировали цитату. Это хорошо. Однако вы их неправильно процитировали, изменив «шесть» на «каждый». Поскольку G & J определяют скупость (т. Е. Число решений точно такое же), Неверно, что каждое сокращение между проблемами в NP можно сделать скупым, ЕСЛИ НЕ P = Parity-P. Причиной этого является то, что стандартное сокращение от SAT до NAE-SAT вводит коэффициент, который является степенью 2. Это ожидается, поскольку SAT завершен для Parity-P, но NAE-SAT прост (есть очевидное сочетание так что ответ всегда четный = 0).

Тайсон Уильямс

Ответы:

Что касается (1), проблема не сильно NP-трудна, см. Следствие 1 здесь :

Пападимитриу, CH (1981). О сложности целочисленного программирования. Журнал ACM , 28 (4), 765-768.

Что касается (2), проблема, очевидно, заключается в #P, если все константы положительны. Существует также # P-полная версия SubsetSum, которая почти соответствует вашему экземпляру проблемы, но требует, чтобы было 0 или 1, см. Здесь : $x_i$

Фалишевский П. и Хемаспандра Л. (2009). Сложность сравнения показателей мощности. Теоретическая информатика 410 (1), 101-107.

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

Кристоф Хааз
источник

Я вообще не специалист по этому вопросу, но я бы хотел начать конструктивное обсуждение. Вот попытка, основанная на вопросе math.stackexchange.com. Подсчитайте количество положительных решений для линейного диофантового уравнения . Материал связан с многочленами Эрхарта, о которых я ничего не знаю, и я думаю также о комментариях @ SashoNikolov выше.

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

a_{N} {Икс}_{N} + a_{N - 1} {Икс}_{N - 1} + \dots + a_{1} {Икс}_{1} знак равно б,

$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}; б) знак равно {\begin{cases} 1 & если a_{1} | б \\ 0 & в противном случае \end{cases}

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

N (a_{1}, ..., a_{N + 1}; б) знак равно \underset{0 \leq К \leq б / a_{N + 1}}{Σ} N (a_{1}, ..., a_{N}; б - a_{N + 1} К)

$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$ «S. Мы знаем, что это будет многочлен в

b

$b$ , но я не вижу, как вычислить полином достаточно быстро.

Андрей Бауэр
источник

Dear Andrej, in case of strong NP-hardness, we measure in terms of the value of the input and not in the length of it. See also: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

domotorp

@domotorp, I think Andrej is addressing the second question, about #P-completeness, not the first about strong NP-completeness, which, as far as I can see, is very easy to answer (no, the problem is not strongly NP-complete). Andrej, I am confused what you are hoping to show here? Since the decision problem is NP-complete, you cannot hope to count the number of solutions. Are you hoping to approximate the number of solutions? Or have a faster-than-exponential time algorithm?

Sasho Nikolov

Кстати, я думаю, что вполне вероятно, что алгоритм в этой статье (приблизительно подсчитывающий количество решений для ранца с помощью динамического программирования) можно адаптировать к задаче диофантовых уравнений: cs.utexas.edu/~klivans/focs11.pdf

Сашо Николов,

Я узнал еще один факт об этой проблеме. Есть три типа людей: те, кто называет это проблемой #linear diophantine, те, кто называет это проблемой #unbound рюкзак, и, наконец, те, кто называет это проблемой денуранта. И они, кажется, не разговаривают друг с другом.

4vergr8ful