Ecuación lineal de diofantina en enteros no negativos

Hay muy poca información que puedo encontrar sobre el problema NP-completo de resolver la ecuación lineal de diofantina en enteros no negativos. Es decir, ¿hay una solución en no negativo para la ecuación , donde todas las constantes son positivas? La única mención notable de este problema que conozco está en la Teoría de la programación lineal y entera de Schrijver . E incluso entonces, es una discusión bastante concisa. $x_1,x_2, ... , x_n$ $a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$

Por lo tanto, agradecería cualquier información o referencia que pueda proporcionar sobre este problema.

Hay dos preguntas que me interesan principalmente:

¿Es fuertemente NP-completo?
¿Es el problema relacionado de contar el número de soluciones # P-hard, o incluso # P-complete?

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

Esto realmente no es una pregunta de nivel de investigación y me resulta difícil creer que no haya encontrado más información. Comience aquí: en.wikipedia.org/wiki/Knapsack_problem

domotorp

para 2), afaik no hay ningún ejemplo conocido de un problema NP-complete cuya versión de conteo natural no sea # P-complete. descubrir una reducción parsimoniosa para su problema particular podría ser más fácil que encontrar una referencia. este documento lo hace para el #SubsetSum estrechamente relacionado: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf

Sasho Nikolov

¿Puedo pedirle a @domotorp y 4evergr8ful un poco más de cortesía? El primero podría haber explicado cómo el problema de la mochila se reduce a tales ecuaciones de Diophantine, lo que parece pensar que es el caso, mientras que 4evergr8ful quizás podría enfriarse, especialmente porque él está pidiendo ayuda y obviamente no tiene experiencia en el funcionamiento de este foro. . Pero también pensé en el problema de la mochila, y no me queda claro en absoluto que se reduzca a soluciones positivas de las ecuaciones de Diophantine.

Andrej Bauer el

OP, como mencionó @Austin, la misma idea de programa dinámico que la mochila funciona para resolver su problema en tiempo polinómico cuando

son polinomiales delimitados. entonces, no, el problema no es fuertemente np-completo. y domotorp tenía una buena razón para indicarle la página wiki de la mochila.

a_{i}

$a_i$

Sasho Nikolov

@ 4evergr8ful Claro, supuse que parafraseaste la cita. Es correcto. Sin embargo, los ha citado mal al cambiar "seis" a "cada". Como G&J define parsimonious (es decir, el número de soluciones es exactamente el mismo), NO es cierto que cada reducción entre problemas en NP pueda hacerse parsimonious A MENOS DE P = Paridad-P. La razón de esto es que la reducción estándar de SAT a NAE-SAT introduce un factor que es una potencia de 2. Esto se espera, ya que SAT está completo para Parity-P pero NAE-SAT es fácil (hay un apareamiento obvio de asignaciones por lo que la respuesta siempre es par = 0).

Tyson Williams el

Respuestas:

Con respecto a (1), el problema no es fuertemente NP-duro, cf Corolario 1 aquí :

Papadimitriou, CH (1981). Sobre la complejidad de la programación de enteros. Revista de la ACM , 28 (4), 765-768.

Con respecto a (2), el problema obviamente radica en #P si todas las constantes son positivas. También hay una versión # P-completa de SubsetSum, que casi encaja en la instancia de su problema pero, sin embargo, requiere que sea 0 o 1, consulte aquí : $x_i$

Faliszewski, P. y Hemaspaandra, L. (2009). La complejidad de la comparación del índice de potencia. Informática teórica 410 (1), 101-107.

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

Christoph Haase
fuente

No soy un experto en esto en absoluto, pero me gustaría comenzar una discusión constructiva. Aquí hay un intento, basado en la pregunta de math.stackexchange.com Cuente el número de soluciones positivas para una ecuación lineal de diofantina . El material está relacionado con los polinomios de Erhart, de los que no sé nada, y creo que también con los comentarios de @ SashoNikolov anteriores.

$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
fuente

Estimado Andrej, en caso de fuerte dureza NP, medimos en términos del valor de la entrada y no en la longitud de la misma. Ver también: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming

domotorp

@domotorp, creo que Andrej está abordando la segunda pregunta, sobre la completitud # P, no la primera sobre la completitud NP fuerte, que, hasta donde puedo ver, es muy fácil de responder (no, el problema no es fuertemente NP -completar). Andrej, ¿estoy confundido con lo que esperas mostrar aquí? Dado que el problema de decisión es NP-completo, no puede esperar contar la cantidad de soluciones. ¿Espera aproximar el número de soluciones? ¿O tiene un algoritmo de tiempo más rápido que exponencial?

Sasho Nikolov

Por cierto, creo que es probable que el algoritmo en este documento (aproximadamente el número de soluciones para la mochila a través de la programación dinámica) se pueda adaptar al problema de la ecuación de diofantina: cs.utexas.edu/~klivans/focs11.pdf

Sasho Nikolov

Aprendí un hecho más sobre este problema. Hay tres tipos de personas: los que lo llaman el problema # lineal de diofantina, los que lo llaman el problema de la mochila #unbound, y finalmente los que lo llaman el problema denumerante. Y no parecen hablar entre ellos.

4evergr8ful