Masalah SUBSET-SUM yang menarik

Saya tahu varian masalah SUBSETSUM berikut: ( Elberfeld at., 2010 ), NP-complete , dan NEXP-complete ( tautan ). $\mathtt{UNARY\mbox{-}SUBSETSUM} \in \mathsf{L}$ $\mathtt{SUBSETSUM}$ $\mathtt{SUCCINCT\mbox{-}SUBSETSUM}$

Baru-baru ini, saya juga mengalami masalah -complete ( Halaman 16: Schaefer and Umans, 2008 ). $\Sigma_2^p$ $\mathtt{GENERALIZED\mbox{-}SUBSETSUM}$

Apakah Anda tahu beberapa varian masalah SUBSETSUM (non-sepele) yang menarik lainnya? Secara khusus, - atau - menyelesaikan masalah untuk beberapa . $\Sigma_l^p$ $\Pi_l^p$ $l > 1$

Beberapa definisi:

$\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 \},$ di mana dan adalah angka biner. $S$ $a_j$

$\mathtt{GENERALIZED\mbox{-}SUBSETSUM} = \{ u \# v \# t \mid (\exists x) (\forall y) [ux+vy \neq t] \},$ mana dan adalah bilangan bulat vektor, adalah bilangan bulat, dan dan adalah vektor biner dengan panjang yang sama dengan dan . $u$ $v$ $t$ $x$ $y$ $u$ $v$

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

salah satu favorit saya adalah PIGEONHOLE-SUBSETSUM yang ada di TFNP ( sciencedirect.com/science/article/pii/030439759190200L ). Yang menarik lainnya adalah EQUALITY-SUBSETSUM ( sciencedirect.com/science/article/pii/S0022000001917842 )

Marcos Villagra

@MarcosVillagra: Terima kasih atas komentar Anda. PIGEONHOLE-SUBSETSUM terlihat menarik. Apakah Anda tahu versi keputusan PIGEONHOLE-SUBSETSUM?

Abuzer Yakaryilmaz

Tidak ada versi keputusan karena batas atas pada penjumlahan memaksa masalah untuk selalu memiliki solusi, maka versi keputusan itu sepele. Buktinya (bahwa selalu ada solusinya) tidak sulit, merupakan penerapan prinsip pigeonhole. Ini adalah referensi yang bagus oleh Papadimitriou ( cs.berkeley.edu/~christos/papers/On%20the%20Complexity.pdf ).

Marcos Villagra

Satu masalah besar yang terbuka adalah untuk membuktikan apakah PIGEONHOLE-SUBSETSUM selesai untuk PPP.

Marcos Villagra

@MarcosVillagra: Terima kasih atas komentar Anda lebih lanjut. Apa yang ada dalam pikiran saya sebenarnya adalah "apakah ada versi masalah keputusan yang nontrivial tapi masih alami dari PIGEONHOLE-SUBSETSUM?". Sebagai contoh, salah satu versi masalah keputusan dari faktorisasi bilangan bulat adalah sebagai berikut: diberi bilangan bulat N dan bilangan bulat M dengan 1 ≤ M ≤ N, apakah N memiliki faktor d dengan 1 <d <M ( en.wikipedia.org/ wiki / Integer_factorization )?

Abuzer Yakaryilmaz

Penghargaan utama harus diberikan kepada John Fearnley !

Berikut ini adalah masalah lengkap PSPACE yang diberikan dalam (John Fearnley, Marcin Jurdzinski: Reachability dalam Two-Time Timed Automata Is PSPACE-Complete. ICALP (2) 2013: 212-223) :

di mana

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

dan masing masing , dan adalah bilangan asli ( ); dan, $S$ $a_i,b_i,e_i$ $f_i$ $1 \leq i \leq n$
untuk setiap , terdapat sehingga $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$

Demikian pula, kita dapat mendefinisikan beberapa masalah lengkap untuk setiap tingkat hierarki polinomial (PH). Tetapi, tentu saja, jika lengkap pada beberapa level PH, kita perlu melepaskan kondisi hanya memiliki dua bilangan alami setelah setiap kuantifier.

Abuzer Yakaryilmaz
sumber

Masalah SUBSET-SUM yang menarik

Jawaban: