Détection des relations entières pour la sous-somme ou NPP?

14

Existe-t-il un moyen de coder une instance de sous-ensemble de somme ou le problème de partition numérique afin qu'une (petite) solution à une relation entière donne une réponse? Si ce n'est pas définitivement, dans un sens probabiliste?

Je sais que LLL (et peut-être PSLQ) ont été utilisés avec un succès modéré dans la résolution des problèmes de sous-ensemble dans la région «à faible densité», où la plage de nombres choisis est supérieure à 2N , mais ces méthodes ne s'adaptent pas bien à des cas de plus grande taille et ne parviennent pas dans la région « haute densité », lorsque la gamme des nombres choisis est beaucoup plus petite que . Ici, basse densité et haute densité se réfèrent au nombre de solutions. La région de faible densité fait référence aux rares ou pas de solutions qui existent alors que la haute densité fait référence à une région avec de nombreuses solutions.2N

Dans la région à haute densité, LLL trouve des (petites) relations entières parmi les instances données, mais à mesure que la taille d'instance augmente, la probabilité que la relation trouvée soit une solution viable de sous-ensemble de somme ou de problème de partition de nombres devient de plus en plus petite.

La détection des relations entières est polynomiale dans une limite exponentielle optimale alors que la sous-somme et NPP sont évidemment NP-Complete, donc en général ce n'est probablement pas possible, mais si l'instance est dessinée uniformément au hasard, cela pourrait-il la rendre plus simple?

Ou ne devrais-je même pas poser cette question et demander à la place s'il existe un moyen de réduire la limite exponentielle de la réponse optimale au lieu d'une augmentation exponentielle du calcul?

cc.complexity-theory np-hardness approximation-algorithms reductions subset-sum user834
la source
Je n'obtenais aucune réponse, j'ai donc posté sur mathoverflow: mathoverflow.net/questions/38063/…
user834
C'est une question très intéressante, j'attends aussi des réponses. Vous demandez essentiellement une réduction du temps polynomial (peut-être aléatoire) de la somme des sous-ensembles ou NPP à la relation entière. Que diriez-vous de cela, si est la cible de votre problème de somme de sous-ensemble, et S est un ensemble d'entiers positifs, avec S ′ une solution satisfaisant 0 = ∑ a ∈ S ′ a . C'est exactement une combinaison linéaire avec des coefficients réels égaux à 1. Si pour chaque vous avez que il y a toujours une solution, et le mappage à la relation entière vous donnera également une solution .t=0SS′0=∑une∈S′uneuneje∈S∑jeuneje<2n-1
Marcos Villagra
@Marcos Villagra: votre commentaire est un peu difficile à analyser ... on peut intégrer le problème comme un problème de partition de somme / nombre de sous-ensemble dans un réseau (voir ici pour une revue), la question est de trouver un moyen de restreindre les coefficients à la ensemble souhaité (0,1 ou -1,1, par exemple). LLL trouvera une relation entière, même petite, mais un seul 2 ou 3 en tant que coefficient l'invalidera comme réponse de partition de sous-ensemble somme / nombre.
user834

Réponses:

2

m=O(Journal⁡n)Ω(2m)m=ω(Journal⁡n)m=o(n)

Cependant, Flaxman et Przydatek fournissent un algorithme qui résout les problèmes de somme de sous-ensembles de densité moyenne dans le temps polynomial attendu.

Vérifiez cette référence:

Flaxman et Przydatek, résolution de problèmes de somme de sous-ensembles de densité moyenne en temps polynomial attendu

Mohammad Al-Turkistany
la source
2
Ce résultat est uniquement pour le choix des nombres dans l'instance de somme de sous-ensemble nettement inférieurs à ce que je veux. Ils choisissent la gamme de nombres dans l'ordre de log (n) ^ 2 alors que je suis intéressant dans la gamme de nombres de l'ordre de 2 ^ n. Il existe des algorithmes bien connus pour résoudre la somme des sous-ensembles lorsque la plage de nombres est restreinte pour être si faible et il semble qu'ils viennent de l'étendre un peu, ce qui est génial, ce n'est tout simplement pas ce que je cherchais. Merci quand même.
user834