Problemas interessantes de SUBSET-SUM

Eu conheço as seguintes variantes de problemas do SUBSETSUM: ( Elberfeld at. Al., 2010 ), NP-complete e NEXP-complete ( link ). $\mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L}$ $\mathtt{SUBSETSUM}$ $\mathtt{SUCCINCT\mbox{-}SUBSETSUM}$

Recentemente, também encontrei o problema -complete ( Página 16: Schaefer e Umans, 2008 ). $\Sigma_2^p$ $\mathtt{GENERALIZED\mbox{-}SUBSETSUM}$

Você conhece outras variantes interessantes (não triviais) dos problemas do SUBSETSUM? Especificamente, - ou - completa problemas para alguns . $\Sigma_l^p$ $\Pi_l^p$ $l > 1$

Algumas definições:

$\mathtt{UNARY\mbox{-}SUBSETSUM} = \{ 0^n \# 0^{i_1} \# \cdots\#0^{i_k} \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}i_j = n \}.$

$\mathtt{SUBSETSUM} = \{ S \# a_1 \# \cdots\# a_k \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}a_j = S \},$ onde e são números binários. $S$ $a_j$

$\mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \},$ onde e são inteiros vetores, é um número inteiro e e são vetores binários do mesmo comprimento que e , respectivamente. $u$ $v$ $t$ $x$ $y$ $u$ $v$

cc.complexity-theory reference-request np-hardness polynomial-hierarchy subset-sum Abuzer Yakaryilmaz
fonte

um dos meus favoritos é PIGEONHOLE-SUBSETSUM, que está no TFNP ( sciencedirect.com/science/article/pii/030439759190200L ). Outro interessante é IGUALDADE-SubsetSum ( sciencedirect.com/science/article/pii/S0022000001917842 )

Marcos Villagra

@MarcosVillagra: Obrigado pelo seu comentário. PIGEONHOLE-SUBSETSUM parece interessante. Você conhece alguma versão de decisão do PIGEONHOLE-SUBSETSUM?

Abuzer Yakaryilmaz

Não há versão de decisão porque o limite superior na soma força o problema a sempre ter uma solução; portanto, a versão da decisão é trivial. A prova disso (que sempre existe uma solução) não é difícil, é uma aplicação do princípio do buraco de pombo. Esta é uma boa referência de Papadimitriou ( cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf ).

Marcos Villagra

Um grande problema em aberto é provar se o PIGEONHOLE-SUBSETSUM está completo para o PPP.

Marcos Villagra

@MarcosVillagra: Obrigado por seus comentários adicionais. O que eu estava pensando é que "existe alguma versão não trivial, mas ainda natural, de um problema de decisão do PIGEONHOLE-SUBSETSUM?". Por exemplo, uma das versões do problema de decisão da fatoração inteira é a seguinte: dado um número inteiro N e um número M com 1 ≤ M ≤ N, N possui um fator d com 1 <d <M ( pt.wikipedia.org/ wiki / Integer_factorization )?

Abuzer Yakaryilmaz

O crédito principal deve ser para John Fearnley !

Aqui está um problema completo do PSPACE apresentado em (John Fearnley, Marcin Jurdzinski: A acessibilidade em autômatos cronometrados com dois relógios é completa no PSPACE. ICALP (2) 2013: 212-223) :

S U B S E T S U M - G A M E = {S \forall (a_{1}, b_{1}) \exists (e_{1}, f_{1}) \dots \forall (a_{n}, b_{n}) \exists (e_{n}, f_{n})},

$\begin{equation} \mathtt{SUBSETSUM\mbox{-}GAME}=\{ S~ \forall(a_1 , b_1) \exists(e_1,f_1) \cdots \forall(a_n , b_n) \exists(e_n,f_n) \}, \end{equation}$ em que

$S$ e cada e são números naturais ( ); e, $a_i,b_i,e_i$ $f_i$ $1 \leq i \leq n$
para cada , existe um modo que . $x=(x_1,\ldots,x_n) \in \times_{i=1}^n \{ a_i,b_i \}$ $y=(y_1,\ldots,y_n) \in \times_{i=1}^n \{ e_i,f_i \}$ $S = \sum_{i=1}^n = x_i+y_i$

Da mesma forma, podemos definir alguns problemas completos para cada nível de hierarquia polinomial (PH). Mas, é claro, no caso de estar completo em algum nível de PH, precisamos liberar a condição de ter apenas dois números naturais após cada quantificador.

Abuzer Yakaryilmaz
fonte

Problemas interessantes de SUBSET-SUM

Respostas: