Detecção de relação inteira para Subset Sum ou NPP?

Existe uma maneira de codificar uma instância de Subset Sum ou o Number Partition Problem para que uma solução (pequena) para uma relação inteira produza uma resposta? Se não definitivamente, então em algum sentido probabilístico?

Eu sei que o LLL (e talvez o PSLQ) foram usados com sucesso moderado na resolução de problemas de Subconjuntos na região 'baixa densidade', onde o intervalo de números escolhido é maior que , mas esses métodos não são bem dimensionados para exemplos de tamanho maior e falhar na região 'de alta densidade', quando o intervalo de números escolhidos é muito menor do que . Aqui baixa densidade e alta densidade se referem ao número de soluções. A região de baixa densidade refere-se às poucas ou nenhumas soluções existentes, enquanto a alta densidade refere-se a uma região com muitas soluções. $2^N$ $2^N$

Na região de alta densidade, a LLL encontra relações inteiras (pequenas) entre instâncias fornecidas, mas à medida que o tamanho da instância aumenta, a probabilidade da relação encontrada ser uma solução viável de Soma de Subconjuntos ou Problema de Partição de Número se torna cada vez menor.

A detecção de relação inteira é polinomial para dentro de um limite exponencial de ideal, enquanto Subset Sum e NPP são obviamente NP-Complete, portanto, em geral, isso provavelmente não é possível, mas se a instância for desenhada uniformemente de forma aleatória, isso poderia torná-lo mais simples?

Ou eu nem deveria estar fazendo essa pergunta e, em vez disso, estar perguntando se existe uma maneira de reduzir o limite exponencial da resposta ótima em vez de um aumento exponencial na computação?

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum user834
fonte

Eu não estava recebendo nenhuma resposta assim que eu cruz enviada para mathoverflow: mathoverflow.net/questions/38063/...

user834

Esta é uma pergunta muito interessante, também estou esperando por respostas. Você está basicamente pedindo uma redução no tempo polinomial (talvez aleatória) da soma do subconjunto ou NPP para a relação inteira. Que tal isso, se é o alvo do seu problema de soma de subconjuntos e é um conjunto de números inteiros positivos, com uma solução que satisfaz . Essa é exatamente uma combinação linear com coeficientes reais iguais a 1. Se para cada você tiver que , sempre haverá uma solução e o mapeamento para a relação inteira também fornecerá uma solução .

t = 0

$t=0$

S

$S$

S^{'}

$S'$

0 = \sum_{a \in S^{'}} a

$0=\sum_{a\in S'} a$

a_{i} \in S

$a_i \in S$

\sum_{i} a_{i} < 2^{n} - 1

$\sum_i a_i < 2^n-1$

Marcos Villagra

@Marcos Villagra: seu comentário é um pouco difícil de analisar ... pode-se incorporar o problema como um problema de partição de soma / número de subconjunto em uma treliça (veja aqui para uma revisão), a questão é encontrar uma maneira de restringir os coeficientes ao conjunto desejado (0,1 ou -1,1, digamos). A LLL encontrará uma relação inteira, mesmo que pequena, mas apenas uma 2 ou 3 como coeficiente a invalidará como resposta de partição de soma / número de subconjunto.

User834

Seja m o logaritmo do maior número. Se , é possível resolver em tempo polinomial usando programação dinâmica. Em geral, todo algoritmo conhecido leva pelo menos tempo. Não há algoritmo de tempo polinomial conhecido quando e $m=O(\log n)$ $\Omega(2^{m})$ $m=\omega(\log n)$ $m=o(n)$

No entanto, Flaxman e Przydatek fornecem um algoritmo que resolve problemas de soma de subconjuntos de densidade média no tempo polinomial esperado.

Verifique esta referência:

Flaxman e Przydatek, resolvendo problemas de soma de subconjuntos de densidade média no tempo polinomial esperado

Mohammad Al-Turkistany
fonte

Esse resultado é apenas para escolher os números na instância Subset Sum significativamente mais baixos do que eu quero. Eles escolhem o intervalo de números na ordem do log (n) ^ 2, enquanto eu sou interessante no intervalo de números na ordem de 2 ^ n. Existem algoritmos conhecidos para resolver o Subconjunto de soma quando o intervalo de números é restrito a ser tão baixo e parece que eles acabaram de estender um pouco esse intervalo, o que é ótimo, não é exatamente o que eu estava procurando. Obrigado mesmo assim.

user834

Detecção de relação inteira para Subset Sum ou NPP?

Respostas: