Kompleksitas Menara Hanoi

Saya mengalami keraguan berikut tentang kompleksitas Menara Hanoi , di mana saya ingin komentar Anda.

Apakah itu dalam NP? Mencoba jawaban: Misalkan Peggy (prover) memecahkan masalah & mengirimkannya ke Victor (pemverifikasi). Victor dapat dengan mudah melihat bahwa keadaan akhir dari solusinya adalah benar (dalam waktu linier) tetapi dia tidak akan memiliki pilihan selain melewati setiap gerakan Peggy untuk memastikan dia tidak melakukan tindakan ilegal. Karena Peggy harus membuat minimal 2 ^ | disk | - 1 gerakan (dapat dibuktikan), Victor juga harus mengikuti. Dengan demikian Victor tidak memiliki verifikasi waktu polinomial (definisi NP), dan karenanya tidak dapat dalam NP.
Apakah itu di PSPACE ? Sepertinya begitu, tapi saya tidak bisa memikirkan cara memperluas alasan di atas.
Apakah PSPACE-selesai? Sepertinya tidak, tapi saya hanya punya ide yang kabur. Perencanaan Otomatis, yang ToH adalah contoh spesifik, adalah PSPACE-complete. Saya pikir Perencanaan memiliki contoh yang jauh lebih sulit daripada ToH.

Diperbarui : Input = $n$ , jumlah disk; Output = konfigurasi disk pada setiap langkah. Setelah memperbarui ini, saya menyadari bahwa format input / output ini tidak sesuai dengan masalah keputusan. Saya tidak yakin tentang formalisasi yang tepat untuk menangkap gagasan tentang NP, PSPACE, dll. Untuk masalah seperti ini.

Pembaruan # 2 : Setelah komentar Kaveh dan Jeff, saya terpaksa membuat masalahnya lebih tepat:

Biarkan input menjadi pasangan int mana adalah jumlah disk. Jika urutan langkah yang diambil oleh disk dituliskan dalam format (nomor-disk, dari-pasak, ke-pasak) (nomor-disk, dari-pasak, ke-pasak) ... dari langkah pertama ke terakhir, dan dikodekan dalam biner, output bit ke- . $(n,i)$ $n$ $i$

Beri tahu saya jika saya harus lebih spesifik tentang pengkodean. Saya kira komentar Kaveh berlaku dalam kasus ini?

complexity-theory time-complexity PKG
sumber

bisakah Anda mendefinisikan masalah Menara Hanoi atau tautan ke sebuah definisi?

Kaveh

PKG, aku tahu apa itu Menara Hanoi. Maksud saya masalah komputasi apa yang ingin Anda ketahui kerumitannya? Apa inputnya? Apa outputnya?

Kaveh

@Kaveh: Niat Anda tidak jelas dari komentar pertama Anda

PKG

Maaf. Btw, ada kelas kompleksitas fungsi, mereka biasanya memiliki F sebelum atau setelah nama, periksa kebun binatang kompleksitas untuk definisi.

Kaveh

Jadi apakah integer

juga bagian dari input?

i

$i$

JeffE

Jawaban:

Tidak, masalah yang Anda uraikan sebenarnya cukup mudah. Alasan tingkat tinggi adalah bahwa indeks kira-kira bit panjang, sehingga kita benar-benar mampu menghabiskan waktu polinomial dalam . $i$ $n$ $n$

Pertimbangkan masalah terkait berikut: Diberikan dua bilangan bulat dan , jelaskan langkah ke- dalam solusi puzzle disk. Ukuran input adalah , tetapi pada kenyataannya, hanya sedikit yang paling signifikan dari penting. Jadi, bahkan jika secara signifikan lebih kecil dari , kita dapat menyelesaikan masalah ini dalam polinomial waktu dalam . $n$ $k$ $k$ $n$ $\lg n + \lg k < n + \lg k$ $n$ $\lg k$ $n$ $O(\log k)$

$0$ $k = (2p+1)\cdot 2^d$ $p$ $d$ $k$

$d+n$ $d$ $(p\bmod 3)$ $((p+1)\bmod 3)$
Jika genap, maka disk bergerak membentuk pasak ke pasak . $d+n$ $d$ $(-p\bmod 3)$ $((-p-1)\bmod 3)$

Kita dapat dengan mudah menghitung dan dalam waktu dengan mengulangi melalui representasi biner dari bit yang paling signifikan ke atas. Itu dia. $p$ $d$ $O(\log k)$ $k$

Sekarang anggaplah Anda benar-benar ingin bit ke- dalam urutan output, di mana adalah bagian dari input, bukan . Jika setiap belokan dikodekan menggunakan jumlah bit yang sama - khususnya, bit untuk nomor disk, bit untuk dari-pasak, dan bit untuk ke-pasak - maka kita hanya perlu menghitung langkah th, di mana , dan kemudian mengekstrak bit yang sesuai. (Perhatikan bahwa linier dalam ukuran input, karena kita perlu tahu untuk menentukan output.) $i$ $i$ $k$ $\lg(n+1)$ $2$ $2$ $k$ $k = \lfloor{i/(\lg(n+1)+4)\rfloor}$ $\lg(n+1)+4$ $n$

Di sisi lain, jika kita menggunakan representasi panjang variabel untuk nomor disk, maka kita dapat menemukan nomor pemindahan dalam waktu polinomial dengan pencarian biner. Kita perlu mengetahui jumlah putaran yang diperlukan untuk memindahkan disk teratas , untuk semua , tetapi ini diberikan oleh pengulangan yang dapat kita evaluasi dalam waktu polinomial dengan pemrograman dinamis. Detail yang tersisa dibiarkan sebagai latihan yang membosankan bagi pembaca. $k$ $m$ $m\le k$

M (m) = 2 M (m - 1) + (\#bits to record moving disk m)

$M(m) = 2M(m-1) + (\text{\#bits to record moving disk } m)$

(Saya berasumsi saya telah membuat setidaknya satu kesalahan satu per satu atau paritas, tapi semoga ide utamanya jelas.)

JeffE
sumber