Masalah Super Mario Galaxy

Misalkan Mario sedang berjalan di permukaan sebuah planet. Jika dia mulai berjalan dari lokasi yang diketahui, ke arah yang tetap, untuk jarak yang telah ditentukan, seberapa cepat kita dapat menentukan di mana dia akan berhenti?

$P$$s$$P$$v$$p$$\ell$$P$$P$

$P$$s$$v$$\ell$

$P$$O(1)$$\ell$$P$

(Dalam praktiknya, panjang jalur sebenarnya tidak terikat; ada batas atas global dalam hal jumlah bit yang diperlukan untuk mewakili input. Tetapi bersikeras pada input integer menimbulkan beberapa masalah numerik yang agak buruk - Bagaimana kita menghitung dengan tepat di mana untuk berhenti? - jadi mari kita tetap berpegang pada input nyata dan menghitung aritmatika nyata.)

Apakah ada yang tidak diketahui tentang kompleksitas masalah ini?

$n$$[0,1]^2$$(0,1/2)$$(1,0)$$\lfloor \ell \rfloor$$\lfloor \ell \rfloor$$O(\log \ell)$$n$$\log \ell$

Masalah ini sangat sangat sulit. Kita bisa menyederhanakannya agar lebih mudah, sebagai berikut.

1. $P$$\pi$

2. Kita dapat mengasumsikan bahwa polytope tidak benar-benar tiga dimensi, tetapi sebaliknya adalah "ganda" dari sebuah poligon; ini terlihat seperti sarung bantal. Kita dapat menyederhanakan lebih jauh dan mengira bahwa poligon memiliki sisi yang sama dan sejajar; misalnya bujur sangkar, seperti pada game Astroids.

$O(\log(\ell))$

Jika kita tidak menganggap rasionalitas, tetapi berasumsi bahwa polytope adalah dobel poligon, maka kita sedang mendiskusikan teori "memotong urutan dalam biliar irasional". Tampaknya pada dasarnya tidak ada yang diketahui di sini; misalnya, lihat kalimat terakhir dari ceramah ini oleh Corinna Ulcigrai.

Jika kita tidak membuat asumsi, well, saya tidak bisa memikirkan apa pun dalam literatur.

$O(\log(\ell))$

Saya pikir Anda bisa melakukan yang lebih baik daripada linear. Saya baru mengenal ilmu komputer teoretis, jadi maafkan saya jika ini adalah sampah.

Beberapa gagasan umum (dengan nilai bervariasi):

• Jika kita memberi masing-masing segi simbol, orbit Mario di atas mereka dapat digambarkan sebagai string, di mana simbol terakhir dalam string adalah jawabannya.
• Kita dapat mengasumsikan tanpa kehilangan keumuman bahwa Mario mulai di tepi (hanya berjalan mundur dan memperpanjang l ke tepi)
• Ruang 2D dari posisi awal dan sudut dapat dipartisi dengan tepi berikutnya. Jadi mulai dari tepi a, x unit dari bawah, dengan sudut a, kita berakhir di tepi V setelah melewati satu sisi.
• Pada titik itu kita berada di tepi lain dengan orientasi lain, sehingga kita dapat memanggil fungsi secara rekursif untuk membagi ruang menjadi partisi dari string 2-simbol dan seterusnya.
• Pada titik ini kita selesai jika kita mengatakan bahwa ruang tersebut harus didiskritisasi agar masalah dapat diimplementasikan pada TM. Itu berarti bahwa setiap orbit harus periodik karena hanya ada banyak titik di planet yang telah didiskritisasi. Kami dapat menghitung fungsi yang dijelaskan di atas sampai kami memiliki orbit untuk semua titik awal dan menyimpan informasi ini. Maka masalahnya menjadi O (1).
• Mungkin itu sedikit masalah. Beberapa googling memberi tahu saya bahwa hampir semua orbit biliar di dalam poligon cembung rasional bersifat periodik (mis. Orbit periodik padat). Jadi untuk planet-planet persegi katakanlah pendekatan yang sama mungkin berhasil.
• Pendekatan lain adalah dengan mempertimbangkan sistem sebagai generator / pengenal string (sekali lagi dengan menetapkan masing-masing segi simbolnya sendiri). Jika bahasa tersebut memiliki kelas kompleksitas yang diketahui, itulah jawaban Anda. Jika Anda memperluas keluarga polytopes menjadi non-cembung dan dimensi apa pun, Anda dapat menangkap kelas bahasa yang sangat luas.

Ini sebenarnya bukan jawaban, tetapi saya harus kembali bekerja. :)