Soma do subconjunto vs. produto do subconjunto (dureza NP forte vs. fraca)

Eu esperava que alguém pudesse me explicar por que exatamente o problema do produto do subconjunto é fortemente NP-difícil, enquanto o problema da soma do subconjunto é fracamente NP-difícil.

Subconjunto Soma: Dado e , existe um subconjunto tal que $X = \{x_1,...,x_n\}$ $T$ $X'$ $\sum_{i\in X'}x_i = T$ .

Subconjunto do produto: Dado e , não existe um subconjunto tal que . $X = \{x_1,...,x_n\}$ $T$ $X'$ $\prod_{i\in X'}x_i = T$

Eu sempre pensei que os dois problemas eram equivalentes - uma instância do SS poderia ser transformada em uma instância do SP via exponenciação e uma instância do SP para SS via logaritmos. Isso me levou a concluir que os dois pertenciam à mesma classe de NP-hard - ou seja, ambos eram fracamente NP-hard.

Além disso, parece que a mesma recorrência pode ser usada para resolver ambos os problemas usando programação dinâmica com uma alteração muito pequena (substituindo subtração em SS por divisão em SP).

Isso foi até eu ler o capítulo 8 de "Teoria da computação", de Bernard Moret (para aqueles que não têm o livro, ele tem uma prova de dureza do produto do subconjunto via X3C - um problema fortemente difícil de NP).

Entendo a redução, mas não consigo descobrir o que havia de errado com minha conclusão anterior (equivalência dos dois problemas).

ATUALIZAÇÃO : Acontece que o produto do subconjunto é apenas fracamente NP completo (o produto de destino é exponencial em ). Gary e Johnson publicaram isso na coluna NP-completeness em 1981 , mas acho que era menos visível do que a afirmação anterior em seu livro. $\Omega (n)$

cc.complexity-theory np-hardness reductions subset-sum RDN
fonte

Provavelmente, seria bom imaginar como você implementaria seu algoritmo de programação dinâmica. Então, você descobriria o que estava errado.

Yoshio Okamoto

@ MohammadAl-Turkistany: Está na seção final desta coluna

RDN 28/03

Respostas:

Em relação ao problema de equivalência da Soma do Subconjunto e do Produto do Subconjunto Existe um detalhe técnico referente ao Produto do Subconjunto. O produto de x's = T é na verdade psuopolinomial se T não for exponencial! Portanto, as provas de que o Subset Product é NP Hard não são (por razões técnicas !!!) muito corretas!

No entanto, dada a promessa de que T é grande, a redução via Logaritmos para Subconjunto dá um SOM DE SUBSET NÃO NORMAL, que está acima dos reais! Isso significa que o algoritmo Psuedopolinomial para Subconjunto de soma não se aplica! Embora os logaritmos sejam pequenos, as casas decimais atrapalham a Programação Dinâmica Psuedopolinomial!

Eu espero que isso ajude

Zelah

Zelah 02
fonte

Acontece que você estava certo o tempo todo sobre as reduções estarem incorretas (ou seja, alegando que elas mostram forte completude de NP, quando não mostram). Obrigado!

RDN 28/03

Em primeiro lugar, o uso da exponenciação para ir do SS para o SP funciona (usando a base 2 em vez da base ), mas aumenta o tamanho dos números envolvidos. Uma dureza NP fraca significa que, se os números forem pequenos (ou mais precisamente, indicados como unários), o problema não será mais difícil. Portanto, o uso da exponenciação cria instâncias de tamanho exponencial do SP, mesmo para as instâncias fáceis do SS, em que os números são escritos em unário. $e$

Em segundo lugar, o uso de logaritmos para ir de SP para SS não funciona, pois os logaritmos geralmente geram valores não inteiros. SS e SP são definidos usando números inteiros, e os logaritmos geralmente resultam em valores transcendentais, difíceis de representar ou fazer contas.

<edit>

Seja um número inteiro, , então o é racional se, e somente se for uma potência de 2, e transcendental de outra forma. Em primeiro lugar, se $A$ $A > 0$ $\log_2 A$ $A$ para inteiros diferentes de zeroe, então $\log_2 A = \frac{p}{q}$ $p$ $q$ ,. Portanto, temos quepor decomposição primária. Além disso, para que uma dadapodemos escolherepara provaré racional. $A = 2^{\frac{p}{q}}$ $A^q = 2^p$ $A = 2^r$ $A^{rq} = 2^p$ $A$ $q=1$ $p=r$ $\log_2 A$

Só precisamos mostrar que o nunca é transcendental. Isso se segue do teorema de Gelfond-Schneider , para uma formulação equivalente (como pode ser encontrada na página da Wiki) é "se e são números algébricos diferentes de zero e tomamos qualquer logaritmo diferente de zero de , então é racional ou transcendental. " Também é fácil de verificar tomando o inverso do teorema e definindo e, portanto, $\log_2 A$ $\alpha$ $\gamma$ $\alpha$ $(\log \gamma)/(\log \alpha) = \log_\alpha \gamma$ $\alpha^\beta = \gamma$ . $\beta = \log_\alpha \gamma$

</edit>

Por fim, considere o que acontece quando tentamos o algoritmo de programação dinâmica do SS no SP. Como usamos produtos em vez de somas, os números envolvidos aumentam enormemente, e a matemática arbitrária de precisão necessária de repente se torna um fator no tempo de execução. É por isso que o algoritmo não pode resolver instâncias de SP rapidamente, mesmo que os números estejam unários.

Alex ten Brink
fonte

isso leva a um caso especial um tanto interessante. para que classe de números os log's são expressáveis como racionais e não exigem precisão infinita? nesse caso, os problemas seriam quase equivalentes e redutíveis um ao outro. também parece levar a um algoritmo de aproximação "natural".

vzn

Obrigado pela ótima resposta! Eu tenho apenas um problema - eu entendo por que pegar logs é ilegal (exceto, talvez, no caso em que os logs tenham comprimento poli - como vzn aponta), mas ainda não tenho certeza sobre a legalidade de ir de SS para SP via exponenciação. O WRT passando de SS para SP, como você mencionou (via exponenciação), não encontramos o seguinte problema: O número de bits na instância de entrada de

e o número de bits no A instância de

. Esta é uma explosão exponencial. Então, ainda é legal? Se for, por que?

I_{S S}

$I_{SS}$

O (n \log x)

$O(n\log x)$

I_{S P}

$I_{SP}$

O (n x)

$O(nx)$

RDN 25/03

@vzn, RDN: editei uma caracterização quando o logaritmo é transcendental. Sobre a explosão da redução, ela depende da sua definição de 'legal': a redução está correta , mas sua eficiência não é polinomial e, portanto, não diz nada sobre a dureza NP. Portanto, não é uma redução correta no tempo de polissemia, mas é uma redução correta (sem qualificadores).

Alex ten Brink

Também há um caso especial em que todos os números estão no formulário

c^{n_{i}}

$c^{n_i}$ , cada

n_{i}

$n_i$ racional, para qualquer

c

$c$ , não apenas

c = 2

$c=2$ . o algoritmo de aproximação que eu estava pensando poderia encontrar um

c

$c$ such that the conversion of values into that "base" is "close" to the originals.

vzn

The literal explanation is that Subset Product problem is NP-complete by a reduction from strongly NP-complete problem such as exact cover by 3-sets. In such "strong" reduction, the input integers are bounded by some polynomial function in the number of integers in the resulting instance of Subset Product problem.

Such a "strong" reduction is impossible from any strongly NP-complete problem to Subset Sum Problem unless $P=NP$ . We have polynomial-time dynamic programming algorithm for solving Subset Sum problem if input integers are bounded by a polynomial.

Mohammad Al-Turkistany
fonte

Yes, I understand that. My question was about why the conclusion I had made earlier was incorrect (i.e., equivalence of SS and SP).

RDN

@rdn There are not equivalent in that sense unless P =NP.

Mohammad Al-Turkistany

Yes, I get that. But I want to know what was wrong with my reductions in either direction.

RDN

Can you outline you reductions?

Mohammad Al-Turkistany

Let

I (S S) = ⟨ X, S ⟩

$I(SS)=\langle X, S \rangle$ be an instance of SS and

I (S P) = ⟨ Y, P ⟩

$I(SP)=\langle Y, P \rangle$ be an instance of SP. Transforming

I (S S)

$I(SS)$ into

I (S P)

$I(SP)$ : Let

P = e^{S}

$P = e^S$ and

Y_{i} = e^{X_{i}}

$Y_i = e^{X_i}$ . There exists a SS of sum

S

$S$ iff there exists a SP of product

P = e^{S}

$P = e^S$ . Transforming

I (S P)

$I(SP)$ into

I (S S)

$I(SS)$ : Let

S = l o g (P)

$S = log(P)$ and

X_{i} = \log (Y_{i})

$X_i = \log(Y_i)$ . There exists a SP of product

P

$P$ iff there exists a SS of sum

S = \log (P)

$S = \log(P)$ .

RDN