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

16

Существует очень мало информации, которую я могу найти по NP-полной задаче решения линейного диофантового уравнения в неотрицательных целых числах. То есть, есть решение в неотрицательном к уравнению 1 х 1 + 2 х 2 + . , , + a n x n = b , где все константы положительны? Единственное заслуживающее упоминания упоминание об этой проблеме, о которой я знаю, - в книге Шрайвера.x1,x2,...,xNa1x1+a2x2+...+anxn=бТеория линейного и целочисленного программирования . И даже тогда это довольно лаконичное обсуждение.

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

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

  1. Это сильно NP-Complete?
  2. Связанная проблема подсчета количества решений # P-hard или даже # P-complete?
4evergr8ful
источник
5
Это действительно не вопрос исследовательского уровня, и мне трудно поверить, что вы не нашли больше информации. Начните здесь: en.wikipedia.org/wiki/Knapsack_problem
domotorp
3
для 2) afaik не существует известного примера NP-полной задачи, чья версия с естественным счетом не # P-полная. выяснить экономное сокращение вашей конкретной проблемы может быть проще, чем найти ссылку. эта статья делает это для тесно связанного #SubsetSum: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf
Сашо Николов
8
Могу ли я спросить у @domotorp и 4evergr8ful немного вежливости? Первый мог бы объяснить, как проблема ранца сводится к таким диофантовым уравнениям, что, как он, кажется, считает, имеет место, в то время как 4evergrful может, возможно, остыть, тем более что он одновременно просит помощи и явно неопытен в работе этого форума , Но я думал и о проблеме ранца, и мне совершенно не ясно, что она сводится к положительным решениям диофантовых уравнений.
Андрей Бауэр
6
OP, как упомянул @Austin, та же идея динамической программы, что и для ранца, решает вашу проблему за полиномиальное время, когда ограничены полиномами. так что нет, проблема не сильно np-полная. и у domotorp была веская причина указать вам на страницу вики о рюкзаке. aя
Сашо Николов
4
@ 4evergr8ful Конечно, я предположил, что вы перефразировали цитату. Это хорошо. Однако вы их неправильно процитировали, изменив «шесть» на «каждый». Поскольку G & J определяют скупость (т. Е. Число решений точно такое же), Неверно, что каждое сокращение между проблемами в NP можно сделать скупым, ЕСЛИ НЕ P = Parity-P. Причиной этого является то, что стандартное сокращение от SAT до NAE-SAT вводит коэффициент, который является степенью 2. Это ожидается, поскольку SAT завершен для Parity-P, но NAE-SAT прост (есть очевидное сочетание так что ответ всегда четный = 0).
Тайсон Уильямс

Ответы:

1

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

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

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

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

xi{0,1}

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

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

N(a1,a2,...,aN;б)

aNИксN+aN-1ИксN-1++a1Икс1знак равноб,
aяб
N(a1;б)знак равно{1если a1|б0в противном случае
N(a1,...,aN+1;б)знак равноΣ0 К б/aN+1N(a1,...,aN;б-aN+1К)
Теперь сумма немного длинна (измеряется по длине входных данных), но мы могли бы надеяться найти лучший способ ее вычисления, чем на самом деле пройти через все К«S. Мы знаем, что это будет многочлен вб, но я не вижу, как вычислить полином достаточно быстро.
Андрей Бауэр
источник
1
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
2
@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
1
Кстати, я думаю, что вполне вероятно, что алгоритм в этой статье (приблизительно подсчитывающий количество решений для ранца с помощью динамического программирования) можно адаптировать к задаче диофантовых уравнений: cs.utexas.edu/~klivans/focs11.pdf
Сашо Николов,
3
Я узнал еще один факт об этой проблеме. Есть три типа людей: те, кто называет это проблемой #linear diophantine, те, кто называет это проблемой #unbound рюкзак, и, наконец, те, кто называет это проблемой денуранта. И они, кажется, не разговаривают друг с другом.
4vergr8ful