Apakah ada pengurangan untuk game “door and pressure plate” yang tidak meledak panjang solusinya?

Makalah ini memberikan bukti bahwa dalam permainan dengan pintu dan pelat penekan, sulit bagi PSPACE untuk menentukan apakah avatar (pemain) dapat mencapai lokasi tertentu. Ini dibuktikan dengan pengurangan dari TQBF , dan lamanya solusi yang dihasilkan tergantung secara eksponensial pada jumlah quantifiers universal dalam formula.

Apakah ada pengurangan dari mesin NPSPACE ke game seperti itu yang panjangnya solusi game secara polinomi terkait dengan panjang jalur penerimaan mesin?

reductions nondeterminism pspace Jeffε
sumber

sketsa singkat tentang tantangan "permainan dengan pintu dan pelat tekanan" yang lebih formal [sayangnya, tidak benar-benar diberikan di koran di satu tempat]. permainan umum adalah peta 2d tak terbatas yang dapat direpresentasikan sebagai grafik (ukuran sewenang-wenang) dari ruang / wilayah penghubung. node dari grafik adalah spasi / daerah (equiv, sel / terowongan dll), ujungnya adalah pintu di antara mereka. pelat tekanan adalah sakelar yang terkandung di dalam ruang. sakelar mengontrol bukaan pintu. pintu mulai dalam keadaan sewenang-wenang, mungkin beberapa terbuka, beberapa tertutup. (dll.) ... namun, tampaknya penulis hanya mempertimbangkan grafik planar.

vzn

lebih jauh lagi, pertanyaannya tampaknya dekat dengan, atau hampir setara, dengan pertanyaan apakah panjang jalur minimal dari suatu solusi (dihitung dalam tepian) melalui grafik secara polinomi atau eksponensial terkait dengan ukuran grafik / sakelar. .. ini pada gilirannya tampaknya terkait erat dengan pertanyaan tentang berapa banyak siklus di jalan diperlukan atau jika mereka tidak ...

vzn

Jawaban:

Mungkin Anda dapat dengan mudah mensimulasikan LBA; idenya adalah sebagai berikut:

$G_i$
$C_i$ $C_i$
$Z_i$ $O_i$ $Z_i$ $O_i$
$q_i$ $i$ $q_i$
$C_i$ $C_{i+1}$ $C_{i-1}$

Gadget sel dibuat sketsa pada gambar di bawah ini.

masukkan deskripsi gambar di sini

Pilihan non-deterministik dapat direalisasikan membagi koridor dalam struktur kontrol menjadi dua atau lebih sub-koridor seperti yang ditunjukkan pada gambar di bawah ini.

masukkan deskripsi gambar di sini

Catatan: jika pelat hanya dapat membuka / menutup satu pintu, maka Anda dapat menambahkan struktur bantu dengan koridor panjang (panjang) yang (de) mengaktifkan pintu keadaan berbeda dari setiap sel.

Marzio De Biasi
sumber

Jika sebuah pintu hanya bisa dibuka oleh satu plat dan hanya bisa ditutup oleh satu plat, maka Anda bisa menggunakan gadget crossover (yang bisa saya uraikan) untuk membiarkan koridor mengarah hanya ke pintu masuk sel yang diinginkan (yang menghilangkan butuhkan untuk pintu C1), implementasikan Z1 dan O1 dengan banyak pintu berbeda, yang masing-masing memiliki pelat penutup segera setelahnya, dan implementasikan pintu q0, ..., q4 sebagai banyak koridor mini dengan masing-masing dua pintu diikuti oleh sebuah piring yang menutup salah satu dari dua pintu itu dan sebuah piring yang menutup salah satu pasangan pintu yang terbuka di qi [nilai sel] lainnya.

$\;\;\;$

Secara independen dari saran dalam komentar saya sebelumnya, jika LBA non-deterministik maka

$\hspace{.2 in}$ koridor satu arah akan membutuhkan sub-koridor, untuk menunjukkan pilihan yang tidak deterministik.

$\hspace{.6 in}$

?? bukankah pengakuan LBA = (N) PSPACE? tampaknya akan lebih membantu jika jawabannya diungkapkan dalam istilah kelas kompleksitas.

vzn

@ RickyDemer: ok, saya menambahkan contoh pilihan non-deterministik. Apakah Anda menggunakan metatheorem Viglietta untuk membuktikan kompleksitas beberapa game?

Marzio De Biasi

Saya sedang membaca metatheorem-nya, dan menyadari bahwa ini adalah satu hal yang tidak mereka bicarakan.

$\hspace{.69 in}$

Cara cepat lain untuk membuktikan Metatheorem 2c (PSPACE-hardness ketika pintu dikontrol oleh dua lempeng) adalah dengan menggunakan kerangka kerja Constraint Logic Nondeterministic ( RA Hearn dan ED Demaine, The Nondeterministic Constraint Logic Model of Computation: Reductions and Applications ).

Dalam hal ini cukup menggunakan seri horizontal dari koridor-pasangan vertikal. Keadaan setiap pasangan koridor mewakili arah (ke dalam / ke luar) dari suatu tepi dalam grafik kendala asli. Cukup untuk mensimulasikan gadget AND dan ATAU gadget, seperti digambarkan pada gambar di bawah ini.

masukkan deskripsi gambar di sini

Marzio De Biasi
sumber

-5

jenis penelitian terkait video game dengan kompleksitas komputasi ini cukup menarik tetapi juga cukup baru, umumnya berusia kurang dari satu dekade. Saya akan berpendapat di sini ada kehalusan yang kadang-kadang terlewatkan dalam analisis saat ini [belum melihat / memperhatikan hal ini ditunjukkan dalam makalah yang dikutip atau makalah lain sejauh ini] dan yang menghambat menjawab pertanyaan yang dinyatakan dengan pasti.

untuk membuktikan hubungan dengan sistem komputasi, seseorang harus dapat memetakan sistem komputasi ke dalam game dan sebaliknya. misalnya dalam makalah yang dikutip di atas oleh Viglietta ada konsep bahwa pelat dan pintu penekan (yaitu pintu pelat kontrol) dapat "seperti" QBF. analogi ini tentu saja layak karena mereka telah memetakannya. seseorang dapat menggunakan QBF untuk menyelesaikan permainan dengan pelat dan pintu bertekanan.

Namun, di sini adalah kehalusannya. dalam game tertentu, tata letak game pada dasarnya sudah diperbaiki. dalam desain gim video konsep tata letak yang berbeda disebut "desain tata letak" dan bukan "diberikan" dari semua gim. misalnya dalam game terobosan Doom, alat desain level bersumber terbuka yaitu dibuat tersedia untuk pemain untuk digunakan. dengan kata lain desain level sewenang-wenang dapat dianggap sebagai bagian dari permainan. tetapi di gim lain yang dipertimbangkan dalam makalah, gim video yang awalnya dibangun memiliki tingkat yang tetap. Koran-koran terkadang tidak secara eksplisit mempertimbangkan hal ini.

oleh karena itu ada argumen kuat untuk dibuat bahwa dalam sebagian besar game tanpa desain level, atau tata letak acak, levelnya tetap, dan ini memiliki dampak besar pada kompleksitas aktual dari penyelesaian "game". yaitu, apa sebenarnya "permainan" itu? apakah itu termasuk tata letak acak, dan / atau kemungkinan desain level? Apakah desain tingkat bagian dari pemetaan komputasi? masalah-masalah ini agak terselip di koran saat ini.

dibawa ke ekstrem yang berlawanan dari makalah, orang bisa berpendapat bahwa semua implementasi video game nyata dapat dipecahkan oleh FSM karena mereka memiliki memori yang terbatas !

agar ada pemetaan komputasi nyata, pada dasarnya kita harus menggeneralisasi permainan untuk terlibat

level dengan ukuran sewenang-wenang! sehingga ini dapat dipetakan ke TM dengan kaset "input" ukuran sewenang-wenang / tidak terbatas.
desain level yang memungkinkan terciptanya level-level ini.

masalah pemetaan yang sedikit mirip muncul dalam penelitian CA / Cellular Automata di mana ada ide tentang menggunakan pola periodik tak terbatas pada CA sebagai "pola awal" untuk membuktikan kesetaraan / kelengkapan TM.

jadi secara umum pertanyaan Anda tidak secara ketat ditentukan sampai Anda mengklarifikasi lebih baik (yaitu lebih formal / matematis mendefinisikan ) apa yang Anda maksud dengan "dalam permainan dengan pintu dan pelat tekanan" dan dengan cara yang bahkan kertas itu tampaknya tidak secara ketat mendefinisikan, terutama wrt untuk ide-ide tentang desain level, level ukuran tidak terbatas, dan sebagainya. tetapi perhatikan bahwa "gim-gim" yang didefinisikan dengan fitur-fitur ini kemudian disarikan dari gim-gim video aktual / nyata dengan cara yang sangat signifikan.

jadi singkatnya saya pikir ini adalah penelitian yang menarik / bermanfaat, meskipun dimulai sebagai agak informal, dan pantas untuk kemajuan lebih lanjut, tetapi sampai taraf tertentu formalisasi harus dibuat lebih ketat terutama dalam definisi dasar jika ingin maju lebih jauh. ia harus membuat perbedaan yang lebih ketat / formal / transparan antara implementasi dan abstraksi .

vzn
sumber

misalnya di sini adalah makalah tentang Battleship sebagai NP lengkap, tetapi lebih baik / secara resmi menyatakan / menggambarkan generalisasi lengkap NP dari game ukuran terbatas. Kapal perang sebagai masalah keputusan oleh Sevenster, bagian kedua.

vzn

contoh lain dari seluk-beluk dalam menggeneralisasi / mengabstraksi masalah, generalisasi dari 15-puzzle geometri dapat mempengaruhi kelengkapan NP-nya . perhatikan kotak persegi vs persegi panjang dapat mempengaruhi hasil.

vzn

Meskipun ini adalah masalah, saya pikir klaim Anda bahwa ini disorot dalam literatur terlalu dilebih-lebihkan. Dan mengingat keberadaan makalah seperti Fraenkel et al FOCS 1978 tentang kompleksitas checker, Even dan Tarjan JACM 1976 tentang Hex, dan Robertson dan Munro Util. Matematika 1978 tentang Kegilaan Instan, klaim Anda bahwa ini adalah area baru juga dilebih-lebihkan.

David Eppstein

jelas gim-gim yang dipelajari secara umum dari tampilan TCS bukanlah hal baru, gim - gim videonya adalah, karena teksnya cermat untuk dinyatakan.

vzn

Mahjong solitaire : 1994. Minesweeper : 2000. Tetris : 2002. Apakah ini tidak dianggap sebagai video game, atau apakah Anda menggunakan dekade yang panjang ?

Peter Shor