El problema subconjuntos de suma y la solvencia de NP-completo los problemas

Question

que estaba leyendo sobre el problema subconjunto sumas cuando vine con lo que parece ser un algoritmo de propósito general para resolverlo:

(defun subset-contains-sum (set sum) 
    (let ((subsets) (new-subset) (new-sum)) 
     (dolist (element set) 
      (dolist (subset-sum subsets) 
       (setf new-subset (cons element (car subset-sum))) 
       (setf new-sum (+ element (cdr subset-sum))) 
       (if (= new-sum sum) 
        (return-from subset-contains-sum new-subset)) 
       (setf subsets (cons (cons new-subset new-sum) subsets))) 
      (setf subsets (cons (cons element element) subsets))))) 

"set" es una lista que no contiene duplicados y "sum" es la suma de los subconjuntos de búsqueda. "subconjuntos" es una lista de células de cons donde el "automóvil" es una lista de subconjuntos y el "cdr" es la suma de ese subconjunto. Se crean nuevos subconjuntos a partir de los antiguos en el tiempo O (1) simplemente considerando el elemento al frente.

No estoy seguro de cuál es la complejidad del tiempo de ejecución, pero parece que con cada elemento "suma" crece, el tamaño de "subconjuntos" se duplica, más uno, por lo que me parece al menos cuadrático.

Lo publico porque mi impresión anterior era que los problemas NP-completos tienden a ser insolubles y que lo mejor que se puede esperar es una heurística, pero esta parece ser una solución de uso general que, asumiéndote tener los ciclos de la CPU, siempre le dará la respuesta correcta. ¿Cuántos otros problemas NP-completos se pueden resolver como este?

Answer 1

Todos los problemas de NP-complete tienen soluciones. Siempre y cuando esté dispuesto a pasar el tiempo para calcular la respuesta, eso es todo. El hecho de que no haya un algoritmo eficiente, no significa que no haya uno. Por ejemplo, podría iterar sobre cada solución potencial, y eventualmente obtendrá una. Estos problemas se usan en todas partes en la computación del mundo real. Solo debes tener cuidado con respecto a la forma en que te planteas un gran problema si vas a necesitar un tiempo exponencial (¡o algo peor!) Para resolverlo.

Answer 2

NP-los problemas completos son solucionables, solo que no en tiempo polinomial (hasta donde sabemos). Es decir, un problema NP-complete puede tener un algoritmo O(n*2^n) que podría resolverlo, pero no tendrá, por ejemplo, un algoritmo O(n^3) para resolverlo.

Curiosamente, si se encuentra un algoritmo rápido (polinomial) para cualquier problema NP-completo, entonces cada problema en NP podría resolverse en tiempo polinomial. De esto se trata P = NP.

Si entiendo su algoritmo correctamente (y esto se basa más en sus comentarios que en el código), entonces es equivalente al algoritmo O(n*2^n)here. Existen 2^n subconjuntos, y como también es necesario sumar cada subconjunto, el algoritmo es O(n*2^n).

Una cosa más sobre la complejidad: el O(whatever) solo indica qué tan bien se escala un algoritmo en particular. No puede comparar dos algoritmos y decir que uno es más rápido que el otro basado en esto. La notación Big-O no se preocupa por los detalles de implementación y las optimizaciones; es posible escribir dos implementaciones del mismo algoritmo, siendo una de ellas mucho más rápida que la otra, aunque ambas podrían ser O(n^2). Una mujer que está criando bebés es una operación O(n), pero es probable que esto tome mucho más tiempo que la mayoría de las O(n*log(n)). Todo lo que puede decir en base a esto es que la ordenación será más lenta para valores muy grandes en n.

Answer 3

no estoy seguro de lo que el tiempo de ejecución complejidad de la que es, pero parece ser que con cada elemento de "suma" crece por, el tamaño de "subgrupos" dobles, más uno, por lo que me parece al menos sea cuadrático.

Si el tiempo de ejecución se duplica para cada aumento en N, está viendo un algoritmo O (2^N). Eso es también lo que esperaría de visitar todos los subconjuntos de un conjunto (o todos los miembros del conjunto de poder de un conjunto), ya que son exactamente 2^N miembros (si incluye el conjunto vacío).

El hecho de que agregar o no agregar un elemento a todos los conjuntos visualizados hasta ahora es rápido no significa que el procesamiento total sea rápido.

Answer 4

Lo que está pasando aquí podría expresarse mucho más simple uso de la recursividad:

 
(defun subset-sum (set sum &optional subset) 
    (when set 
    (destructuring-bind (head . tail) set 
     (or (and (= head sum) (cons head subset)) 
      (subset-sum tail sum   subset) 
      (subset-sum tail (- sum head) (cons head subset)))))) 

Las dos llamadas recursivas al final muestran claramente que estamos atravesando un árbol binario de profundidad n, el tamaño del conjunto dado . El número de nodos en el árbol binario es O (2^n), como se esperaba.

Answer 5

Es karpreducible al tiempo polinomial. Reducir con reducción de Karp a un problema de decisión O (nM) usando un límite superior de búsqueda binaria o de heap es log (M * 2^M) = logM + log (2^M) = logM + Mlog2 Tiempo de Ergo: O (nM)