J'espérais que quelqu'un pourrait m'expliquer pourquoi exactement le problème de produit de sous-ensemble est fortement NP-difficile alors que le problème de somme de sous-ensemble est faiblement NP-difficile. Somme Sous - ensemble: Étant donné X= { x1, . . . , xn}X={X1,...,Xn}X = \{x_1,...,x_n\}...
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...
On nous donne un graphe acyclique dirigé G = ( V, E)g=(V,E)G=(V,E) avec un nombre associé à chaque sommet ( ), et un nombre cible .g: V→ Ng:V→Ng:V\to \mathbb{N}T∈ NT∈NT\in \mathbb{N} Le problème de somme de sous-ensemble DAG (peut exister sous un nom différent, une référence sera excellente)...
J'ai une réduction du problème de partition suivant à un certain problème de planification: Entrée: Une liste une1⩽ ⋯ ⩽ anune1⩽⋯⩽unena_1\leqslant\cdots\leqslant a_n d'entiers positifs dans l'ordre non décroissant. Question: Existe-t-il un vecteur ( x1, … , Xn) ∈ { - 1 , 1...
Nous savons que sous ETHETHETH nous ne pouvons pas résoudre KKK -SUM en temps F( K) p o l y( n K)F(K)poly(nK)f(K)poly(nK) sous n'importe quelle fonction F( K)F(K)f(K) (généralement 2O ( K)2O(K)2^{O(K)} ). Y a-t-il une conjecture qui empêche une complexité ( journaln )O ( K)(Journaln)O(K)(\log...