Apa kompleksitas game ini?

Ini adalah generalisasi dari pertanyaan saya sebelumnya .

Mari menjadi mesin deterministik waktu polinomial yang dapat mengajukan pertanyaan untuk beberapa oracle . Awalnya kosong tetapi ini dapat diubah setelah permainan yang akan dijelaskan di bawah ini. Biarkan menjadi beberapa string. $M$ $A$ $A$ $x$

Pertimbangkan permainan Alice dan Bob berikut ini. Awalnya, Alice dan Bob memiliki dan dolar masing-masing. Alice ingin dan Bob ingin . $m_A$ $m_B$ $M^A(x)=1$ $M^A(x)=0$

Di setiap langkah permainan, pemain dapat menambahkan beberapa string ke ; ini menghabiskan biaya dolar, di mana adalah fungsi yang dihitung waktu polinomial. Juga seorang pemain dapat melewatkan langkahnya. $y$ $A$ $f(y)$ $f: \{0,1\}^* \to \mathbb{N}$

Permainan berakhir jika kedua pemain menghabiskan semua uang atau jika beberapa pemain melewatkan langkah ketika dia dalam posisi kalah (yang ditentukan oleh nilai saat ini dari $M^A(x)$ ).

Pertanyaan: apakah masalah menentukan pemenang game ini untuk $M, f, x, m_A, m_B$ adalah

EXPSPACE -Tugas lengkap?

Perhatikan bahwa dapat meminta (untuk milik ) hanya string panjang polinomial sehingga tidak ada rasa untuk Alice atau Bob menambahkan string lebih lama untuk . Karenanya, masalah ini ada di EXPSPACE . $M$ $A$ $A$

Dalam pertanyaan saya sebelumnya menambahkan setiap string ke biaya satu dolar (yaitu ). Kemudian (seperti yang ditunjukkan oleh Lance Fortnow ) game ini milik EXPH dan bahkan PSPACE jika . $A$ $f \equiv 1$ $m_A = m_B$

cc.complexity-theory complexity-classes gt.game-theory Alexey Milovanov
sumber

Bisakah Anda menjelaskan mengapa Anda membuat perubahan ini ke masalah? Alice dapat memeriksa untuk melihat apakah dia mampu membayar semua string dalam (sebagaimana didefinisikan dalam jawaban Lance untuk masalah Anda yang lain) dalam waktu polinomial. Bagaimana ini tidak segera menyelesaikan masalah?

S

$S$

Stella Biderman

@StellaBiderman Alice memang dapat memeriksa ini dalam waktu polinomial. Namun, jika dia tidak memiliki cukup uang maka sekarang ini tidak berarti bahwa dia hanya dapat membuat langkah polinomial (seperti pada permainan sebelumnya).

Alexey Milovanov

Jika dia tidak mampu membeli , bisakah dia mengalahkan lawan yang selalu melewatkan giliran mereka? Mungkin ada sesuatu tentang pengaturan game yang saya tidak mengerti.

S

$S$

Stella Biderman

@Stella Ya, karena mereka mungkin jalur penerimaan lainnya. Misalnya, misalkan jika , maka berhenti dan menerima. Dalam hal ini, . Tetapi jika , maka mungkin permintaan dan menerima jika

. Dalam hal ini sudah cukup jika Alice memiliki cukup spondulix untuk .

x_{1} \in A

$x_1\in A$

M

$M$

S = {x_{1}}

$S=\{x_1\}$

x_{1} \notin A

$x_1\notin A$

M

$M$

x_{2}

$x_2$

x_{2} \in A

$x_2\in A$

x_{2}

$x_2$

domotorp

Jawaban:

Ini harus EXPSPACE-complete. Saya akan membuat sketsa bagaimana mencapai sejumlah alternatif eksponensial, tanpa mengurangi masalah EXPSPACE-lengkap untuk yang satu ini, tetapi dari sini seharusnya mudah untuk diselesaikan.

Nyatakan kata-kata dalam oracle setelah $t$ rounds oleh $A_t$ , jadi awalnya $A_0=\emptyset$ . Menunjukkan kata-kata ditanyakan oleh $M^{A_t}$ oleh $Q_t$ . Pengamatan utama adalah bahwa siapa pun yang kalah dengan $A_t$ , dapat diasumsikan untuk menambahkan sesuatu dari $Q_t$ ke $A$ . Ini karena dalam permainan ini setiap gerakan membutuhkan biaya, kami ingin bergerak sesedikit mungkin; tidak ada gunanya bergerak sampai kita menang. Tapi ini juga menyiratkan bahwa jika kita kehilangan, tidak ada gunanya menambahkan apa-apa dari luar $Q_t$ .

Asumsikan untuk kesederhanaan bahwa $M$ berjalan tepat untuk $2n$ langkah dan pada langkah $2i$ dan $2i+1$ itu permintaan kata panjang persis $i$ . Fungsi biaya $f$ hanya akan $2^{-i}$ pada kata kata panjang $i$ . Game ini akan rupa sehingga Alice selalu perlu menambahkan kata-kata panjang aneh dan Bob selalu perlu menambahkan kata-kata panjang bahkan $A$ . Misalkan $n$ itu aneh dan awalnya Alice kalah.

Anggaran $m_A$ dan $m_B$ akan ditetapkan sehingga ia dapat memilih tepat satu dari panjang $n$ kata ditanyakan oleh $M^{A_0}$ untuk ditambahkan ke $A$ . Permainan akan sedemikian rupa sehingga ini membuatnya menjadi pemenang, jadi Bob harus pindah. Sekali lagi karena keterbatasan anggaran, ia akan harus memilih tepat satu dari panjang $n-1$ kata ditanyakan oleh $M^{A_1}$ yang akan ditambahkan ke $A$ . Setelah salah satu dari ini ditambahkan, $M^{A_2}$ akan meminta dua panjang $n$ kata baru (yang sama, terlepas dari apa kata Bob ditambahkan ke $A$ ), dan Bob akan menang. Alice akan dipaksa untuk menambahkan tepat salah satu dari panjang baru ini $n$ kata-kata ke $A$ untuk membuatnya menang.

Permainan berjalan dengan cara ini, yang dapat dibayangkan sebagai mengikuti cabang-cabang pohon biner lengkap kedalaman $n$ , meskipun pada setiap node bercabang salah satu pemain (ditentukan yang oleh paritas kedalaman node) perlu membuat pilihan tentang mana kata untuk menambah $A$ . Setelah mereka melewati pohon, mereka akan kehabisan anggaran mereka. Jika pada setiap tahap permainan salah satu dari mereka memutuskan untuk menambahkan beberapa kata yang lebih pendek (mis. Alice a length $k<n$ word from $Q_0$ pada langkah pertama), maka jika pemain lain (dalam contoh kita Bob) hanya memainkan selalu kata terpanjang yang dia bisa di pohon biner, dia akan memiliki uang tersisa di akhir dan kita membuat permainan sehingga dia bisa menggunakan ini untuk menang. (Perhatikan bahwa Alice mungkin juga memiliki sisa uang, tetapi Bob akan memiliki lebih banyak, jadi kami merancang permainan akhir bahwa jika salah satu dari mereka memiliki lebih banyak uang, maka pemain itu dapat menang.)

Dengan cara ini Alice memutuskan untuk secara berpasangan banyak pasangan kata-kata panjang aneh, dan Bob tentang banyak kata-kata panjang panjang secara eksponensial yang satu dari masing-masing pasangan pergi ke $A$ , dan mereka membuat pilihan ini secara bergantian.

domotorp
sumber

Terima kasih atas jawaban Anda. Saya mengajukan beberapa pertanyaan kepada Anda melalui email.

Alexey Milovanov