Equação diofantina linear em números inteiros não negativos

16

Há muito pouca informação que eu possa encontrar sobre o problema NP-completo de resolver a equação diofantina linear em números inteiros não negativos. Ou seja, existe uma solução em não negativo para a equação , onde todas as constantes são positivas? A única menção digna de nota desse problema que conheço está na Teoria da Programação Linear e Inteira de Schrijver . E mesmo assim, é uma discussão bastante concisa.x1 1,x2,...,xnuma1 1x1 1+uma2x2+...+umanxn=b

Portanto, eu apreciaria muito qualquer informação ou referência que você pudesse fornecer sobre esse problema.

Existem duas perguntas que mais me interessam:

  1. É fortemente NP-Complete?
  2. O problema relacionado de contar o número de soluções # P-hard, ou até # P-complete?
4evergr8ful
fonte
5
Esta não é realmente uma questão de nível de pesquisa e acho difícil acreditar que você não tenha encontrado mais informações. Comece aqui: pt.wikipedia.org/wiki/Knapsack_problem
domotorp 12/11/13
3
para 2), após um exemplo conhecido de um problema de NP completo cuja versão natural de contagem não é # P-completa. descobrir uma redução parcimoniosa para seu problema específico pode ser mais fácil do que encontrar uma referência. Neste artigo faz isso para o #SubsetSum intimamente relacionados: crt.umontreal.ca/~gerardo/tsppd-p-complete.pdf
Sasho Nikolov
8
Posso pedir a @domotorp e 4evergr8ful um pouco mais de civilidade? O primeiro poderia ter explicado como o problema da mochila se reduz a essas equações diofantinas, o que ele parece pensar que é o caso, enquanto 4evergr8ful pode talvez esfriar, especialmente porque ele está pedindo ajuda e obviamente não tem experiência no funcionamento deste fórum. . Mas pensei também no problema da mochila, e não está claro para mim que isso se reduz a soluções positivas das equações diofantinas.
11303 Andrej Bauer #
6
OP, como o @Austin mencionou, a mesma ideia de programa dinâmico da mochila funciona para resolver seu problema no tempo polinomial quando os são limitados por polinômios. portanto, não, o problema não está fortemente completo. e a domotorp tinha um bom motivo para apontar você para a página wiki da mochila. ai
Sasho Nikolov
4
@ 4evergr8ful Claro, presumi que você parafraseasse a citação. Está bem. No entanto, você os citou incorretamente alterando "seis" para "todos". Como G&J define parcimonioso (ou seja, o número de soluções é exatamente o mesmo), NÃO é verdade que toda redução entre problemas em PN pode ser parcimoniosa, a menos que P = Paridade-P. A razão para isso é que a redução padrão de SAT para NAE-SAT introduz um fator que é uma potência de 2. Isso é esperado, uma vez que o SAT é completo para a Paridade-P, mas o NAE-SAT é fácil (existe um emparelhamento óbvio de atribuições para que a resposta seja sempre par = 0).
Tyson Williams

Respostas:

1

Em relação a (1), o problema não é fortemente NP-rígido, conforme o Corolário 1 aqui :

Papadimitriou, CH (1981). Sobre a complexidade da programação inteira. Jornal da ACM , 28 (4), 765-768.

Em relação a (2), o problema obviamente está no #P se todas as constantes forem positivas. Há também uma versão # P-complete do SubsetSum, que quase se encaixa na instância do problema, mas exige que o seja 0 ou 1, veja aqui :xEu

Faliszewski, P. e Hemaspaandra, L. (2009). A complexidade da comparação do índice de potência. Teórico Computer Science 410 (1), 101-107.

xEu{0 0,1 1}

Christoph Haase
fonte
0

Não sou especialista nisso, mas gostaria de iniciar uma discussão construtiva. Aqui está uma tentativa, com base na pergunta math.stackexchange.com Conte o número de soluções positivas para uma equação diofantina linear . O material está relacionado aos polinômios de Erhart, sobre os quais não sei nada, e também penso nos comentários de @ SashoNikolov acima.

N(uma1 1,uma2,...,uman;b)

umanxn+uman-1 1xn-1 1++uma1 1x1 1=b,
umaEub
N(uma1 1;b)={1 1E se uma1 1b0 0de outra forma
N(uma1 1,...,uman+1 1;b)=0 0 k b/uman+1 1N(uma1 1,...,uman;b-uman+1 1k)
kb
Andrej Bauer
fonte
11
Caro Andrej, em caso de forte dureza NP, medimos em termos do valor da entrada e não em sua extensão. Veja também: en.wikipedia.org/wiki/Knapsack_problem#Dynamic_programming
domotorp 13/11/13
2
@domotorp, acho que Andrej está abordando a segunda pergunta, sobre # P-completeness, não a primeira sobre forte NP-completeness, que, até onde eu posso ver, é muito fácil de responder (não, o problema não é fortemente NP -completo). Andrej, estou confuso o que você espera mostrar aqui? Como o problema de decisão é NP-completo, você não pode esperar contar o número de soluções. Você espera aproximar o número de soluções? Ou possui um algoritmo de tempo mais rápido que o exponencial?
Sasho Nikolov
11
BTW, acho que é provável que o algoritmo deste artigo (aproximadamente o número de soluções para a mochila via programação dinâmica) possa ser adaptado ao problema da equação diofantina: cs.utexas.edu/~klivans/focs11.pdf
Sasho Nikolov
3
Aprendi mais um fato sobre esse problema. Existem três tipos de pessoas: aqueles que chamam de problema diofantino linear, aqueles que chamam de problema da mochila não ligada e, finalmente, aqueles que chamam de problema denumerante. E eles não parecem conversar um com o outro.
4evergr8ful