Interessante SUBSET-SUM-Probleme

Ich kenne die folgenden Varianten von SUBSETSUM-Problemen: ( Elberfeld at. Al., 2010 ), NP-vollständige und NEXP-vollständige ( Link ). $\mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L}$ $\mathtt{SUBSETSUM}$ $\mathtt{SUCCINCT\mbox{-}SUBSETSUM}$

Vor kurzem bin ich auch auf das Problem gestoßen - ( Seite 16: Schaefer und Umans, 2008 ). $\Sigma_2^p$ $\mathtt{GENERALIZED\mbox{-}SUBSETSUM}$

Kennen Sie einige andere (nicht triviale) interessante Varianten von SUBSETSUM-Problemen? Insbesondere vervollständigen - oder - Probleme für einige . $\Sigma_l^p$ $\Pi_l^p$ $l > 1$

Einige Definitionen:

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

wobei und ‚s sind binär Zahlen. $\mathtt{SUBSETSUM} = \{ S \# a_1 \# \cdots\# a_k \mid \exists I \in \{1,\ldots,k\} \sum_{j \in I}a_j = S \},$ $S$ $a_j$

wobei und sind ganzzahlige Vektoren, ist eine ganze Zahl und und $\mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \},$ $u$ $v$ $t$ $x$ sind binäre Vektoren mit der gleichen Länge wie bzw. . $y$ $u$ $v$

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

Einer meiner Favoriten ist PIGEONHOLE-SUBSETSUM in TFNP ( sciencedirect.com/science/article/pii/030439759190200L ). Ein weiteres interessantes ist EQUALITY-SUBSETSUM ( sciencedirect.com/science/article/pii/S0022000001917842 )

Marcos Villagra

@MarcosVillagra: Danke für deinen Kommentar. PIGEONHOLE-SUBSETSUM sieht interessant aus. Kennen Sie eine Entscheidungsversion von PIGEONHOLE-SUBSETSUM?

Abuzer Yakaryilmaz

Es gibt keine Entscheidungsversion, da die Obergrenze der Summierung das Problem zwingt, immer eine Lösung zu haben, daher ist die Entscheidungsversion trivial. Der Beweis dafür (dass es immer eine Lösung gibt) ist nicht schwierig, ist eine Anwendung des Pigeonhole-Prinzips. Dies ist eine nette Referenz von Papadimitriou ( cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf ).

Marcos Villagra

Ein großes offenes Problem besteht darin, zu beweisen, ob PIGEONHOLE-SUBSETSUM für PPP vollständig ist.

Marcos Villagra

@MarcosVillagra: Vielen Dank für Ihre weiteren Kommentare. Was ich dachte, ist tatsächlich, dass "es eine nicht triviale, aber immer noch natürliche Version von Entscheidungsproblemen von PIGEONHOLE-SUBSETSUM gibt?". Zum Beispiel ist eine der Entscheidungsproblemversionen der Ganzzahlfaktorisierung wie folgt: Wenn eine ganze Zahl N und eine ganze Zahl M mit 1 ≤ M ≤ N gegeben sind, hat N einen Faktor d mit 1 <d <M ( en.wikipedia.org/) wiki / Integer_factorization )?

Abuzer Yakaryilmaz

Der Hauptkredit sollte an John Fearnley gehen !

Hier ist ein PSPACE-vollständiges Problem in (John Fearnley, Marcin Jurdzinski: Erreichbarkeit in zeitgesteuerten Automaten mit zwei Takten ist PSPACE-vollständig. ICALP (2) 2013: 212-223) :

S. U. B. S. E. T. S. U. M. - - G EIN M. E. = {S. \forall ({ein}_{1}, b_{1}) \exists (e_{1}, f_{1}) \dots \forall ({ein}_{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}$

und jedes und sind natürliche Zahlen ( ); und, $S$ $a_i,b_i,e_i$ $f_i$ $1 \leq i \leq n$
für jedes existiert ein so, dass $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$

In ähnlicher Weise können wir einige vollständige Probleme für jede Ebene der Polynomhierarchie (PH) definieren. Aber natürlich müssen wir im Falle einer vollständigen PH-Stufe die Bedingung aufheben, dass nach jedem Quantifizierer nur zwei natürliche Zahlen vorliegen.

Abuzer Yakaryilmaz
quelle

Interessante SUBSET-SUM-Probleme

Antworten: