Problemas interesantes de SUBSET-SUM

Conozco las siguientes variantes de problemas SUBSETSUM: ( Elberfeld at. Al., 2010 ), NP-complete , y NEXP-complete ( enlace ). $\mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L}$ $\mathtt{SUBSETSUM}$ $\mathtt{SUCCINCT\mbox{-}SUBSETSUM}$

Recientemente, también me encontré con el problema -complete ( Página 16: Schaefer y Umans, 2008 ). $\Sigma_2^p$ $\mathtt{GENERALIZED\mbox{-}SUBSETSUM}$

¿Conoces otras variantes interesantes (no triviales) de los problemas de SUBSETSUM? Específicamente, - o - completa problemas para algunos . $\Sigma_l^p$ $\Pi_l^p$ $l > 1$

Algunas definiciones

$\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 \},$ donde y son números binarios. $S$ $a_j$

$\mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \},$ donde y son enteros vectores, es un número entero, y e son vectores binarios de la misma longitud que y , respectivamente. $u$ $v$ $t$ $x$ $y$ $u$ $v$

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

uno de mis favoritos es PIGEONHOLE-SUBSETSUM que se encuentra en TFNP ( sciencedirect.com/science/article/pii/030439759190200L ). Otro interesante es EQUALITY-SUBSETSUM ( sciencedirect.com/science/article/pii/S0022000001917842 )

Marcos Villagra

@MarcosVillagra: Gracias por tu comentario. PIGEONHOLE-SUBSETSUM parece interesante. ¿Conoces alguna versión de decisión de PIGEONHOLE-SUBSETSUM?

Abuzer Yakaryilmaz

No hay una versión de decisión porque el límite superior de la suma obliga al problema a tener siempre una solución, por lo tanto, la versión de decisión es trivial. La prueba de ello (que siempre hay una solución) no es difícil, es una aplicación del principio del casillero. Esta es una buena referencia de Papadimitriou ( cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf ).

Marcos Villagra

Un gran problema abierto es probar si PIGEONHOLE-SUBSETSUM está completo para PPP.

Marcos Villagra

@MarcosVillagra: Gracias por sus comentarios adicionales. Lo que estaba en mi mente es en realidad que "¿hay alguna versión de problema de decisión no trivial pero aún natural de PIGEONHOLE-SUBSETSUM?". Por ejemplo, una de las versiones con problemas de decisión de la factorización de enteros es la siguiente: dado un entero N y un entero M con 1 ≤ M ≤ N, ¿N tiene un factor d con 1 <d <M ( en.wikipedia.org/ wiki / Integer_factorization )?

Abuzer Yakaryilmaz

¡El crédito principal debe ir a John Fearnley !

Aquí hay un problema de PSPACE completo en (John Fearnley, Marcin Jurdzinski: La accesibilidad en autómatas temporizados de dos relojes es PSPACE completo. ICALP (2) 2013: 212-223) :

donde

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}$

y cada y son números naturales ( ); y, $S$ $a_i,b_i,e_i$ $f_i$ $1 \leq i \leq n$
por cada , existe a tal 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$

Del mismo modo, podemos definir algunos problemas completos para cada nivel de jerarquía polinómica (PH). Pero, por supuesto, en caso de estar completo en algún nivel de PH, necesitamos liberar la condición de tener solo dos números naturales después de cada cuantificador.

Abuzer Yakaryilmaz
fuente

Problemas interesantes de SUBSET-SUM

Respuestas: