Équation diophantienne linéaire en entiers non négatifs

Il n'y a que très peu d'informations que je peux trouver sur le problème NP-complet de la résolution de l'équation diophantienne linéaire en nombres entiers non négatifs. C'est - à - dire, est - il une solution non négatif à l'équation , où toutes les constantes sont positives? La seule mention notable de ce problème que je connaisse est dans Schrijver $x_1,x_2, ... , x_n$ $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$ Théorie de la programmation linéaire et entière . Et même alors, c'est une discussion plutôt laconique.

J'apprécierais donc grandement toute information ou référence que vous pourriez fournir sur ce problème.

Il y a deux questions qui m'intéressent principalement:

Est-ce fortement NP-Complete?
Le problème lié au comptage du nombre de solutions est-il # P-difficile, voire # P-complet?

cc.complexity-theory reference-request np-hardness counting-complexity 4evergr8ful
la source

Ce n'est vraiment pas une question au niveau de la recherche et j'ai du mal à croire que vous n'avez pas trouvé plus d'informations. Commencez ici: en.wikipedia.org/wiki/Knapsack_problem

domotorp

pour 2), afaik, il n'y a pas d'exemple connu d'un problème NP-complet dont la version de comptage naturel n'est pas # P-complete. déterminer une réduction parcimonieuse de votre problème particulier pourrait être plus facile que de trouver une référence. cet article le fait pour le #SubsetSum étroitement lié: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf

Sasho Nikolov

Puis-je demander à @domotorp et à 4evergr8ful un peu plus de civilité? Le premier aurait pu expliquer comment le problème du sac à dos se réduit à de telles équations diophantiennes, ce qu'il semble penser que c'est le cas, tandis que 4evergr8ful pourrait peut-être se calmer, d'autant plus qu'il demande de l'aide et est évidemment inexpérimenté dans le fonctionnement de ce forum . Mais j'ai aussi pensé au problème du sac à dos, et il ne m'est pas du tout clair qu'il se réduit à des solutions positives d'équations diophantiennes.

Andrej Bauer

OP, comme @Austin l'a mentionné, la même idée de programme dynamique que pour le sac à dos fonctionne pour résoudre votre problème en temps polynomial lorsque les

sont bornés par le polynôme. donc, non, le problème n'est pas fortement np-complet. et domotorp avait une bonne raison de vous diriger vers la page wiki du sac à dos.

a_{i}

$a_i$

Sasho Nikolov

@ 4evergr8ful Bien sûr, je suppose que vous avez paraphrasé la citation. Ça va. Cependant, vous les avez mal cités en remplaçant «six» par «chaque». Comme G&J définit la parcimonie (c'est-à-dire que le nombre de solutions est exactement le même), il n'est PAS vrai que chaque réduction entre les problèmes de NP peut être parcimonieuse SAUF P = Parité-P. La raison en est que la réduction standard de SAT à NAE-SAT introduit un facteur qui est une puissance de 2. Ceci est attendu, car SAT est complet pour Parity-P mais NAE-SAT est facile (il existe un appariement évident de affectations de sorte que la réponse est toujours paire = 0).

Tyson Williams

Réponses:

En ce qui concerne (1), le problème n'est pas fortement NP-difficile, voir Corollaire 1 ici :

Papadimitriou, CH (1981). Sur la complexité de la programmation entière. Journal de l'ACM , 28 (4), 765-768.

Concernant (2), le problème réside évidemment dans #P si toutes les constantes sont positives. Il existe également une version # P complète de SubsetSum, qui correspond presque à votre instance de problème mais nécessite cependant que soit 0 ou 1, voir ici : $x_i$

Faliszewski, P. et Hemaspaandra, L. (2009). La complexité de la comparaison des indices de puissance. Informatique théorique 410 (1), 101-107.

Je suis à peu près sûr que la construction utilisée par Faliszewski et Hemaspaandra peut être ajustée de sorte que l'exigence n'est pas nécessaire et prétendrait donc que le problème est # P-complet, à condition que les constantes soient encodées en binaire. $x_i\in \{0,1\}$

Christoph Haase
la source

Je ne suis pas du tout un expert en la matière, mais j'aimerais entamer une discussion constructive. Voici une tentative, basée sur la question math.stackexchange.com Comptez le nombre de solutions positives pour une équation diophantienne linéaire . La substance est liée aux polynômes d'Erhart, dont je ne sais rien, et je pense aussi aux commentaires de @ SashoNikolov ci-dessus.

Définissez comme le nombre de solutions non négatives de l'équation diophantienne où les coefficients sont positifs et non négatifs. Si je fais bien mes récursions, alors nous avons $N(a_1, a_2, \ldots, a_n; b)$

{une}_{n} X_{n} + {une}_{n - 1} X_{n - 1} + \dots + {une}_{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 ({une}_{1}; b) = {\begin{cases} 1 & si {une}_{1} ∣ b \\ 0 & autrement \end{cases}

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

N ({une}_{1}, \dots, {une}_{n + 1}; b) = \sum_{0 \leq k \leq b / {une}_{n + 1}} N ({une}_{1}, \dots, {une}_{n}; b - {une}_{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
la source

Cher Andrej, en cas de forte dureté NP, nous mesurons en fonction de la valeur de l'entrée et non de sa longueur. Voir aussi: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

domotorp

@domotorp, je pense qu'Andrej répond à la deuxième question, à propos de # P-complétude, pas la première à propos de forte NP-compléteness, à laquelle, à ma connaissance, il est très facile de répondre (non, le problème n'est pas fortement NP -Achevée). Andrej, je suis confus ce que vous espérez montrer ici? Comme le problème de décision est NP-complet, vous ne pouvez pas espérer compter le nombre de solutions. Espérez-vous approximer le nombre de solutions? Ou avez-vous un algorithme temporel plus rapide qu'exponentiel?

Sasho Nikolov

BTW, je pense qu'il est probable que l'algorithme de cet article (comptant approximativement le nombre de solutions pour le sac à dos via la programmation dynamique) puisse être adapté au problème de l'équation diophantienne: cs.utexas.edu/~klivans/focs11.pdf

Sasho Nikolov

J'ai appris un fait de plus sur ce problème. Il existe trois types de personnes: ceux qui l'appellent le problème diophantien # linéaire, ceux qui l'appellent le problème du sac à dos #unbound, et enfin ceux qui l'appellent le problème dénumératif. Et ils ne semblent pas se parler.

4evergr8ful