O problema da soma dos subconjuntos e a solubilidade de problemas NP-completos

Question

Eu estava lendo sobre o problema das somas de subconjuntos quando descobri o que parece ser um algoritmo de uso geral para resolvê-lo:

(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)))))

"conjunto" é uma lista que não contém duplicatas e "soma" é a soma para pesquisar subconjuntos."subconjuntos" é uma lista de células cons onde o "carro" é uma lista de subconjuntos e o "cdr" é a soma desse subconjunto.Novos subconjuntos são criados a partir dos antigos no tempo O(1), apenas colocando o elemento na frente.

Não tenho certeza de qual é a complexidade do tempo de execução, mas parece que a cada elemento que a "soma" aumenta, o tamanho dos "subconjuntos" dobra, mais um, então me parece pelo menos quadrático.

Estou postando isso porque minha impressão anterior era que problemas NP-completos tendem a ser intratáveis ​​e que o melhor que se pode esperar é uma heurística, mas esta parece ser uma solução de uso geral que, supondo que você tenha os ciclos de CPU , sempre dê a resposta correta.Quantos outros problemas NP-completos podem ser resolvidos como este?

Answer 1

Todos os problemas NP-completos têm soluções.Contanto que você esteja disposto a gastar tempo para calcular a resposta, claro.Só porque não há eficiente algoritmo, não significa que não exista um.Por exemplo, você poderia simplesmente iterar todas as soluções potenciais e, eventualmente, obteria uma.Esses problemas são usados ​​​​em todos os lugares na computação do mundo real.Você só precisa ter cuidado com o tamanho do problema que definiu para si mesmo, se precisar de tempo exponencial (ou pior!) para resolvê-lo.

Answer 2

Problemas NP-completos são solucionáveis, mas não em tempo polinomial (até onde sabemos).Ou seja, um problema NP-completo pode ter uma O(n*2^n) algoritmo que poderia resolvê-lo, mas não terá, por exemplo, um O(n^3) algoritmo para resolvê-lo.

Curiosamente, se um algoritmo rápido (polinomial) fosse encontrado para qualquer problema NP-completo, então todo problema em NP poderia ser resolvido em tempo polinomial.É disso que se trata P = NP.

Se entendi seu algoritmo corretamente (e isso se baseia mais em seus comentários do que no código), então é equivalente ao O(n*2^n) algoritmo aqui.Há 2^n subconjuntos, e como você também precisa somar cada subconjunto, o algoritmo é O(n*2^n).

Mais uma coisa sobre complexidade - o O(whatever) indica apenas quão bem um algoritmo específico é dimensionado.Você não pode comparar dois algoritmos e dizer que um é mais rápido que o outro com base nisso.A notação Big-O não se preocupa com detalhes e otimizações de implementação - é possível escrever duas implementações do mesmo algoritmo, sendo uma muito mais rápida que a outra, mesmo que ambas possam ser O(n^2).Uma mulher fazendo bebês é uma O(n) operação, mas as chances são de que isso demore muito mais do que a maioria O(n*log(n)) classifica você executa.Tudo o que você pode dizer com base nisso é que a classificação será mais lenta para valores muito grandes em n.

Answer 3

Não tenho certeza de qual é a complexidade do tempo de execução, mas parece que com cada elemento "soma" cresce, o tamanho de "subconjuntos" dobra, mais um, por isso me parece pelo menos ser quadrático.

Se o tempo de execução dobrar para cada aumento em N, você estará olhando para um algoritmo O(2^N).Isso também é o que eu esperaria ao visitar todos os subconjuntos de um conjunto (ou todos os membros do powerset de um conjunto), já que são exatamente 2 ^ N membros (se você incluir o conjunto vazio).

O fato de adicionar ou não um elemento a todos os conjuntos vistos até agora ser rápido não significa que o processamento total seja rápido.

Answer 4

O que está acontecendo aqui poderia ser expresso de maneira muito mais simples usando recursão:

(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))))))

As duas chamadas recursivas no final mostram claramente que estamos percorrendo uma árvore binária de profundidade n, o tamanho do conjunto fornecido.O número de nós na árvore binária é O(2^n), conforme esperado.

Answer 5

É karpreduzível ao tempo polinomial.Reduzir com redução de Karp para um problema de decisão O(nM) usando um heap ou pesquisa binária, os limites superiores são log(M*2^M)=logM+log(2^M)=logM+Mlog2 Ergo Time:O(nM)