Esperaba que alguien pudiera explicarme por qué exactamente el problema del producto del subconjunto es fuertemente NP-duro, mientras que el problema de la suma del subconjunto es débilmente NP-duro. Subconjunto Suma: Dada y , ¿existe un subconjunto tal que .X= { x1, . . . ,
¿Hay alguna forma de codificar una instancia de Subset Sum o el problema de partición numérica para que una solución (pequeña) a una relación entera produzca una respuesta? Si no es definitivamente, ¿en algún sentido probabilístico? Sé que LLL (y quizás PSLQ) se han utilizado con éxito moderado en...
Se nos da un dirigido acíclico gráfico con un número asociado con cada vértice ( g : V → N ), y un número de destino T ∈ N .G=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N}T∈NT∈NT\in \mathbb{N} El problema de la suma DAG subconjunto (podría existir con un nombre diferente, una referencia será...
Tengo una reducción del siguiente problema de partición a un cierto problema de programación: Entrada: Una lista de enteros positivos en orden no decreciente.a1⩽⋯⩽ana1⩽⋯⩽ana_1\leqslant\cdots\leqslant a_n Pregunta: ¿Existe un vector (x1,…,xn)∈{−1,1}n(x1,…,xn)∈{−1,1}n(x_1,\ldots,x_n)\in\{-1,1\}^n...
Sabemos que bajo ETHETHETH no podemos resolver KKK -SUM en el tiempo f(K)poly(nK)f(K)poly(nK)f(K)poly(nK) bajo ninguna función f(K)f(K)f(K) (generalmente 2O(K)2O(K)2^{O(K)} ). ¿Hay alguna conjetura que evite una complejidad (logn)O(K)(logn)O(K)(\log n)^{O(K)} (esto es completamente consistente...
Por "bueno", quiero decir que el algoritmo proporciona un límite relativamente estrecho o tiene un tiempo de ejecución relativamente rápido. Cualquier referencia es
Conozco las siguientes variantes de problemas SUBSETSUM: ( Elberfeld at. Al., 2010 ), NP-complete , y NEXP-complete ( enlace ).S U B S E T S U M S U C C I N C T - S U B S E T S U MUN A R Y - S UB S E T S UM∈LUNARY-SUBSETSUM∈L \mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L} SUBSETSUMETROSUBSETSUM...