Problemas interessantes de SUBSET-SUM

8

Eu conheço as seguintes variantes de problemas do SUBSETSUM: ( Elberfeld at. Al., 2010 ), NP-complete e NEXP-complete ( link ).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 MUNARY-SUBSETSUMLSUBSETSUMSUCCINCT-SUBSETSUM

Recentemente, também encontrei o problema -complete ( Página 16: Schaefer e Umans, 2008 ). G E N E R A G I Z E D - S L B S E T S L MΣ2pGENERALIZED-SUBSETSUM

Você conhece outras variantes interessantes (não triviais) dos problemas do SUBSETSUM? Especificamente, - ou - completa problemas para alguns . Π p l l > 1ΣlpΠlpl>1


Algumas definições:

UNARY-SUBSETSUM={0n#0i1##0ikI{1,,k}jIij=n}.

SUBSETSUM={S#a1##akI{1,,k}jIaj=S}, onde e são números binários.a jSaj

GENERALIZED-SUBSETSUM={u#v#t(x)(y)[ux+vyt]}, onde e são inteiros vetores, é um número inteiro e e são vetores binários do mesmo comprimento que e , respectivamente.v t x y u vuvtxyuv

Abuzer Yakaryilmaz
fonte
2
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
2
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
2
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

Respostas:

1

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

SUBSETSUM-GAME={S (a1,b1)(e1,f1)(an,bn)(en,fn)},
em que
  • S e cada e são números naturais ( ); e,ai,bi,eifi1in
  • para cada , existe um modo que .y = ( y 1 , , y n ) × n i = 1 { e i , f i } S = n i = 1 = x i + y ix=(x1,,xn)×i=1n{ai,bi}y=(y1,,yn)×i=1n{ei,fi}S=i=1n=xi+yi

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