Gim pada beberapa grafik

Pertimbangkan permainan berikut pada grafik tertimbang $G$ diarahkan dengan chip di beberapa node.

Semua node $G$ ditandai dengan A atau B.

Ada dua pemain, Alice dan Bob. Tujuan dari Alice (Bob) adalah untuk menggeser chip ke node yang ditandai oleh A (B).

Awalnya Alice dan Bob memiliki $m_A$ dan $m_B$ dolar masing-masing.

Jika seorang pemain dalam posisi kalah (yaitu, posisi chip saat ini ditandai dengan huruf yang berlawanan) ia dapat memindahkan chip ke node tetangga. Langkah tersebut membutuhkan biaya beberapa dolar (berat tepi yang sesuai).

Pemain kalah jika dia dalam posisi kalah dan tidak punya uang untuk memperbaikinya.

Sekarang perhatikan bahasa GAME yang terdiri dari semua graf berbobot terarah $G$ (semua bobot bilangan bulat positif), posisi awal chip, dan ibukota Alice dan Bob yang diberikan dalam representasi unary

sedemikian rupa sehingga Alice memiliki strategi kemenangan di game ini.

GAME bahasa milik P . Memang, posisi saat ini dari permainan ditentukan oleh posisi chip dan ibukota saat ini dari Alice dan Bob, sehingga pemrograman dinamis bekerja (di sini penting bahwa modal awal diberikan dalam representasi unary).

Sekarang perhatikan generalisasi berikut dari game ini. Mempertimbangkan beberapa diarahkan grafik tertimbang $G_1, \ldots G_n$ dengan chip pada setiap grafik. Semua node dari semua grafik ditandai oleh A dan B. Sekarang Bob menang jika semua chip ditandai oleh B dan Alice menang jika setidaknya satu chip ditandai oleh A.

Pertimbangkan bahasa MULTI-PERTANDINGAN yang terdiri dari semua grafik $G_1, \ldots, G_n$ , posisi awal dan ibukota $m_A$ dan $m_B$ (dalam representasi unary) sehingga Alice menang di pertandingan yang sesuai. Di sini penting bahwa huruf kapital adalah umum untuk semua grafik, jadi, bukan hanya beberapa GAME independen.

Pertanyaan Apa kompleksitas bahasa MULTI-GAMES? (Apakah itu juga milik P atau ada beberapa alasan mengapa masalah ini sulit?)

UPD1 Neal Young menyarankan untuk menggunakan teori Conway. Namun saya tidak tahu apakah mungkin menggunakan teori ini untuk beberapa game dengan modal bersama.

UPD2 Saya ingin menunjukkan contoh yang menunjukkan bahwa MULTI-GAME tidak terlalu sederhana. Biarkan Alice membagi nya modal $m_A$ untuk beberapa $n$ istilah $m_A = a_1 + a_2 + \ldots a_n$ (Dia akan menggunakan $a_i$ dolar untuk $i$ grafik th). Tentukan $b_i$ sebagai jumlah minimal seperti yang di $i$ permainan -th Bob menang jika Alice dan Bob memiliki $a_i$ dan $b_i$ dolar masing-masing. Jika $b_1 + \ldots b_n > m_B$ (untuk beberapa pembagian$m_A = a_1 + a_2 + \ldots a_n$ ) maka Alice menang. Namun, yang terjadi adalah sebaliknya. Pertimbangkan dua salinan grafik berikut (awalnya chip ada di sebelah kiri atas A):

Untuk satu grafik, Bob menang jika $m_A=0$ dan $m_B=2$ atau jika $m_A=1$ dan $m_B=3$ . Namun untuk permainan dengan dua salinan grafik ini Bob kehilangan jika $m_A=1$ dan $m_B=5$ . Memang, Bob harus menghabiskan $4$ atau $5$ dolar untuk menggeser kedua chip ke node ditandai dengan $B$ . Kemudian Alice dapat menggeser setidaknya satu chip ke simpul yang ditandai oleh A. Setelah itu Bob tidak punya uang untuk menyelamatkan posisinya.

UPD3 Karena pertanyaan untuk grafik sewenang-wenang tampaknya sulit, pertimbangkan grafik tertentu. Nyatakan simpul dari beberapa grafik $G_i$ sebagai $1, \ldots k$ . Batasan saya adalah sebagai berikut: untuk setiap pasangan $i<j$ terdapat tepi dari $i$ ke $j$ dan tidak ada tepi terbalik. Juga ada batasan untuk biaya edge: untuk $i<j<k$ edge $j$ ke $k$ tidak lebih besar dari dari $i$ ke $k$ .

Karena jawaban Steven Stadnicki tampaknya tidak diterima oleh penanya, saya pikir mungkin masih bermanfaat untuk memberikan pembaruan: Saya memiliki pengurangan dari 3SAT menjadi MULTI-GAME. Saya belum melihat jawaban Steven dengan hati-hati atau mengikuti tautan yang dia berikan, tetapi berdasarkan pengurangan berikut ini saya tidak akan terkejut jika MULTI-GAME benar-benar menyelesaikan PSPACE. Saya mungkin tidak repot-repot memperluas hasil ini di luar kekerasan NP.

Sebuah 3SAT contoh terdiri dari klausa $C_1, \dots, C_m$ , masing-masing klausa menjadi bentuk $C_i = L_{i1} \vee L_{i2} \vee L_{i3}$ dimana setiap $L_{ik}$ adalah salah satu dari variabel $x_1, \dots, x_n$ atau negasi dari salah satu variabel.

Dengan instance 3SAT yang demikian, pengurangan menciptakan instance MULTI-GAME yang terdiri dari $n + 1$ game - satu untuk setiap variabel dan game lain yang digunakan sebagai capital sink berlebih. Pertama kita akan menentukan struktur grafik untuk setiap game, kemudian melihat contoh dan mendiskusikan ide inti, dan kemudian kita akan mencari tahu berapa biaya yang tepat untuk menentukan tepi agar pengurangan reduksi bertahan.

Pertama, grafik permainan variabel $G_j$ untuk setiap variabel $x_j$ :

1. Buat titik berlabel $x_j$ ditandai dengan A (yaitu titik menang untuk Alice). Chip untuk $G_j$ dimulai pada simpul $x_j$ .
2. Buat simpul bertanda $T$ dan simpul bertanda $F$ , masing-masing ditandai dengan B (yaitu keduanya memenangkan posisi untuk Bob). Buat tepi diarahkan dari $x_j$ untuk kedua $T$ dan $F$ , baik dengan biaya $1$ .

3. Untuk setiap literal $L_{ik}$ dari klausa $C_i$ , jika $L_{ik} = x_j$ atau $L_{ik} = \neg x_j$ , membuat simpul berlabel $C_iTA$ dan $C_iFA$ ditandai dengan A dan simpul berlabel $C_iTB$ dan $C_iFB$ ditandai dengan B. Tambahkan tepi $(T, C_iTA)$ dan$(F, C_iFA)$ dengan biaya yang ditetapkan ke$l_{ik}$ . (Kami akan mendefinisikan$l_{ik}$ nanti.)

   Tambahkan tepi $(C_iTA, C_iTB)$ dan $(C_iTA, C_iTB)$ . Jika $L_{ik} = x_j$ , maka set $(C_iTA, C_iTB)$ biaya ke $l_{ik} - 1$ dan $(C_iTA, C_iTB)$ biaya untuk$l_{ik}$ . Kalau tidak, setel biaya$(C_iTA, C_iTB)$ ke$l_{ik}$ dan$(C_iTA, C_iTB)$ biaya ke$l_{ik} - 1$ .

Permainan capital sink:

1. Buat simpul bertanda $C$ , ditandai dengan B.
2. Untuk setiap klausa $C_i$ , buat simpul bertanda $C_iA$ ditandai dengan A, dan simpul bertanda $C_iB$ ditandai dengan B. Buat tepi $(C, C_iA)$ dengan biaya tepi $c_i$ (lagi ditentukan di bawah) , dan edge $(C_iA, C_iB)$ juga dengan biaya edge $c_i$ .

Ini banyak yang perlu dipertimbangkan, jadi semoga contoh membuat ini lebih mudah dicerna. Contoh 3SAT kami adalah sebagai berikut:

$C_1 = x_1 \vee x_2 \vee \neg x_3$

$C_2 = x_2 \vee x_3 \vee \neg x_4$

$C_3 = \neg x_1 \vee \neg x_3 \vee x_4$

Reduksi mengubah instance ini menjadi 4 grafik game variabel dan 1 grafik capital sink. Dalam diagram di bawah ini, simpul merah ditandai dengan A (yaitu posisi menang untuk Alice), dan simpul cyan ditandai dengan B (posisi menang untuk Bob).

Grafik untuk $x_1$ :

Grafik untuk $x_2$ :

Grafik untuk $x_3$ :

Grafik untuk $x_4$ :

Grafik untuk capital sink:

Idenya adalah sebagai berikut:

Bob dipaksa untuk membuat pertama $n$ bergerak untuk keluar dari kehilangan posisi di $n$ game variabel. Setiap langkah tersebut mengkodekan penugasan benar atau salah ke variabel terkait.

Alice kemudian akan memiliki modal yang cukup untuk membuat tepat 4 langkah, yang masing-masingnya Bob harus memiliki modal yang cukup untuk mencocokkan agar Bob menang. The $c_i$ nilai-nilai dan $l_{ik}$ nilai-nilai yang harus dipilih sehingga hanya mungkin strategi memenangkan Alice adalah sebagai berikut, untuk beberapa klausul $C_i$ :

Strategi Alice clause $C_i$ : biarkan $C_i = L_{i1} \vee L_{i2} \vee L_{i3}$ . Untuk setiap $k \in \{1, 2, 3\}$ , jika $L_{ik} = x_j$ atau $\neg x_j$ , pindah ke $C_i?A$ dalam game variabel untuk $x_j$ . Juga pindah ke $C_iA$ di permainan capital sink.

( $C_i?A$ menunjukkan $C_iTA$ atau $C_iFA$ , hanya satu yang dapat dicapai dalam permainan variabel tertentu setelah gerakan pembukaan Bob.)

Jika pembukaan bersesuaian Bob untuk tugas kebenaran bahwa daun beberapa klausul $C_i$ tidak puas, maka Alice memilih $C_i$ dan menerapkan strategi di atas biaya Alice $l_{i1} + l_{i2} + l_{i3} + c_i$ modal untuk melaksanakan, dan Bob sama untuk mengalahkan; jika di sisi lain $C_i$ puas, maka lawan main Bob mendapat diskon minimal $1$ . Tujuan kami dalam mengatur $c_i$ dan $l_{ik}$ nilai dan modal awal Alice dan Bob adalah untuk memastikan bahwa diskon tersebut adalah faktor penentu apakah Alice atau Bob menang.

Untuk itu, atur $b = m + 1$ , dan atur

$l_{ik} = 2b^{10} + ib^{2k}$ untuk setiap$k \in \{1, 2, 3\}$ ,

$c_i = 3b^{10} + b^8 - \sum_{k=1}^3 ib^{2k}$ ,

Modal awal Alice ke $9b^{10} + b^8$ ,

dan modal awal Bob ke $9b^{10} + b^8 + n - 1.$

Perhatikan bahwa semua nilai ini polinomial dalam $m$ , sehingga turunan MULTI-GAME yang dihasilkan oleh reduksi memiliki ukuran polinomial dalam ukuran instance 3SAT bahkan jika biaya ini dikodekan dalam unary.

Perhatikan juga bahwa untuk setiap klausa $C_i$ , $l_{i1} + l_{i2} + l_{i3} + c_i = 9b^{10} + b^8$ adalah modal awal Alice. (Yang juga $1$ lebih besar dari modal Bob setelah membuat $n$ pertama bergerak.)

Pertama-tama, segera jelas bahwa jika pembukaan Bob mendefinisikan penugasan kebenaran yang membuat klausa $C_i$ tidak puas, maka Alice menang menggunakan strategi klausa $C_i$ yang diberikan di atas.

Jika Bob yang membuka memuaskan semua klausa, kita bisa memperdebatkan batasan pada opsi Alice yang mengesampingkan kemungkinan lain dari kemenangan Alice. Perhatikan bahwa urutan Alice membuat gerakannya tidak relevan, karena respons Bob dipaksakan dan total modal yang diperlukan Bob untuk merespons langkah Alice tidak berubah oleh urutan gerakan Alice.

• Alice tidak dapat melakukan lebih dari 4 gerakan: jika Alice membuat 5 atau lebih gerakan, maka gerakannya memiliki total biaya $\ge 5b^{10}$ , yang melebihi anggarannya.
• Alice harus membuat 4 gerakan: jika Alice memilih 3 gerakan dari permainan capital sink maka total biaya nya adalah $\ge 9b^{10} + 3b^8 - 3b^7 > 9b^{10} + 2b^8$ yang melebihi anggaran. Jika dia memilih satu gerakan 3 saja dari permainan variabel, maka total biaya nya adalah $\le 8b^{10} + 2b^8 + b^7$ yang secara substansial lebih kecil dari modal pasca pembukaan Bob, sehingga Bob dapat dengan mudah membayar lawan mainnya.
• Alice harus memilih langkah dari permainan capital sink: jika dia tidak, maka dia memilih 4 langkah dari game variabel, dengan total biaya $\le 8b^{10} + 4b^7$ , dan sekali lagi Bob dapat dengan mudah membayar lawan mainnya. (Perhatikan bahwa jika ada permainan capital sink terpisah per klausa, kami bahkan dapat menunjukkan bahwa Alice harus bermain tepat dalam satu game seperti itu.)

Dari tahap ini kita dapat mengabaikan persyaratan $b^{10}$ dan $b^8$ dalam biaya perpindahan yang dipilih, karena mereka akan selalu berjumlah $9b^{10} + b^8$ . Sejak Alice harus memilih tepat satu langkah di wastafel ibukota permainan, menganggap bahwa langkah adalah untuk $C_iA$ . Kemudian Alice memiliki (mengabaikan istilah $b^{10}$ dan $b^8$ ) $\sum_{k=1}^3 ib^{2k}$ modal yang tersisa, dan Bob memiliki $1$ kurang dari jumlah ini yang tersisa.

• Alice harus memilih setidaknya satu gerakan dengan biaya $l_{j3}$ untuk beberapa klausa $C_j$ : jika tidak, maka biaya perpindahannya (lagi-lagi syarat pesanan lebih rendah) $\le 3b^5$ , dan Bob memiliki modal lebih dari cukup untuk bermain balik.
• Perpindahan ini mengatakan $l_{j3}$ harus menjadi pemindahan biaya $l_{i3}$ : itu tidak bisa menjadi perpindahan dengan biaya $l_{j3}$ untuk $j > i$ , jika tidak, biaya perpindahan ini saja $\ge (i+1)b^6$ yang lebih besar dari sisa Alice anggaran. Jika $l_{j3}$ untuk $j < i$ , maka biaya $l_{(i - j)3}$ juga harus dipilih oleh Alice untuk menghabiskan $b^6$Istilah -terima dalam sisa anggaran Bob. Tapi kemudian Entah $b^2$ istilah orde kedua di sisa anggaran Bob atau $b^2$ istilah orde kedua tidak mendapatkan kelelahan, sehingga Bob menang dgn mudah.

Argumen serupa harus menetapkan bahwa Alice harus memilih gerakan dengan biaya $l_{i2}$ dan $l_{i1}$ . Jika penugasan kebenaran Bob memuaskan $C_i$ , maka bahkan strategi ini tidak berhasil, karena diskon yang didapat Bob pada salah satu dari biaya berbasis $l_{ik}$ membuat modal kurang dari $1$ ia miliki setelah pembukaannya.

Sebuah komentar pada jawaban saya sebelumnya: jelas di belakang bahwa, untuk varian TABEL-GAME dari MULTI-GAME yang saya definisikan dalam komentar dari jawaban itu, DP gaya ransel cukup untuk menentukan pemain mana yang memiliki strategi kemenangan. Anda dapat berargumen bahwa strategi terbaik Bob adalah selalu merespons keadaan yang hilang dalam tabel permainan tertentu dengan investasi seminimal mungkin (ini tidak dapat memotong langkah selanjutnya untuk Bob yang seharusnya ia lakukan sebaliknya), dan dari sana urutan tersebut pergerakan Alice tidak masalah. Ini kemudian menjadi masalah memilih pemisahan modal Alice di antara permainan sedemikian rupa sehingga jumlah respons kemenangan minimal Bob atas game-game tersebut melebihi anggarannya, yang dapat dibingkai ulang sebagai masalah gaya ransel, yang memiliki DP polinomial waktu ke representasi biaya unary. (Perulangan saya sebenarnya akan '

Ternyata bahkan struktur pohon sederhana untuk setiap game, dengan kedalaman konstan dan benar-benar hanya satu garpu bermakna per game (yaitu yang di awal yang memaksa Bob untuk memilih tugas kebenaran) sudah cukup untuk mendapatkan kekerasan NP. Saya punya beberapa ide untuk menyingkirkan garpu awal itu, yang terhenti karena entah bagaimana memaksa Bob untuk menginvestasikan sejumlah besar modal tetap dalam $n$ game tanpa Alice harus terlebih dahulu berkomitmen untuk game-game sebelumnya, tetapi jelas karena TABLE-GAME ada di P ini tidak mungkin tanpa garpu.

Saya belum terlalu memikirkan case khusus Anda dari UPD3 . Saya menduga itu juga NP-hard, karena alasan variabel gadget saya sekilas sepertinya mereka dapat beradaptasi dengan kendala tersebut, tetapi saya mungkin tidak akan memeriksanya lebih jauh.

Pembaruan: mungkin salah, tersisa untuk saat ini sebagai catatan telah menjelajahi jalan. Lihat komentar.

Pembaruan 2: pasti salah.

Pertimbangkan grafik bentuk (B) -1-> (A) -1-> (B), yaitu $G = (V, E)$ , di mana $V = \{1, 2, 3\}$ , $E = \{(1, 2), (2, 3)\}$ , simpul 1, 2, 3 masing-masing diberi label B, A, B, dan edge adalah semua biaya yang ditetapkan sebesar 1.

Tetapkan instance 3-game MULTI-GAME dengan menetapkan $m_A = m_B = 2$ , $G_1 = G_2 = G_3 = G$ , dengan ketiga game dimulai dari vertex 1. Jelas Alice tidak dapat memenangkan game ini.

Namun, pengulangan di bawah ini gagal untuk $M[3,2,2]$ : tidak ada pemisahan dana Bob $2-u, u$ antara dua game pertama dan game ketiga sehingga untuk semua pembagian dana Alice $v, 2 - v$ , baik $M[2, 2 - u, 2 - v] = B$ dan $W[3, u, v] = B$ . Jika$u = 1$ atau$u = 2$ , lalu$M[2, 2 - u, 2] = A$ ; dan jika$u = 0$ maka$W[3, u, 2] = A$ .

Saya tidak melihat cara langsung untuk menyelamatkan pendekatan ini. Membalik urutan kuantifikasi pada $u$ dan $v$ membuat perulangan gagal pada contoh di pembaruan 2 dari posting pertanyaan.

$m_A, m_B, G_1, \dots, G_n,$

Precompute

$W[k, x, y] = \begin{cases}A & \text{if Alice wins GAME on $G_k$ with initial funds $x$ for Alice and $y$ for Bob,} \\ B & \text{otherwise}\end{cases}$

$x \le m_A$$y \le m_B$

$M[k, x, y]$$k$$x \le m_A$$y \le m_B$$M[k, x, y] = B$$A$

$M[1, x, y] = W[1, x, y]$

dan

$M[k+1, x, y] = B \quad\text{if and only if}\quad \exists v \forall u, W[k+1, u, v] = B \:\:\text{and}\:\: M[k, x-u, y-v] = B.$

$M[n, m_A, m_B] = A$

$[n]$$n+1$$n\ldots 0$$i+1$$i$$0\leq i\lt n$$0$$0$$n$$[n]$$\geq n$$0$$0$

$G$$\alpha$$\beta$$\alpha$$[i]$$\beta$$\beta$$[j]$$[k]$$j\lt k$$\alpha$$\beta$$\beta$$[j]$$[k]$$[k]$$[i]$$\{i\mid\{j\mid k\}\}$