Mungkinkah ini masalah NP-Lengkap?

10

Pertimbangkan pernyataan masalah berikut:

Diberi nomor awal, Anda dan teman Anda bergantian mengurangi kuadrat sempurna darinya. Yang pertama mencapai nol menang. Sebagai contoh:

Status awal: 37

Pemain1 mengurangi 16. Negara: 21

Player2 kurangi 8. Status: 13

Pemain1 mengurangi 4. Negara: 9

Player2 kurangi 9. Status: 0

Player2 menang!

Tulis program yang diberi status awal, kembalikan langkah yang optimal, yaitu program yang dijamin memimpin untuk memenangkan permainan. Jika tidak ada gerakan yang mungkin dapat membawa Anda ke keadaan menang, kembalikan -1.

Masalah ini dapat diselesaikan dalam waktu semu-polinomial menggunakan pemrograman dinamis. Idenya hanya mengisi array panjang n (di mana n adalah keadaan awal) bottom up dengan gerakan optimal, atau -1 jika tidak ada gerakan mengarah ke kemenangan. Ini akan membutuhkan O (n * sqrt (n)) karena untuk setiap angka kita perlu mempertimbangkan mengurangi setiap kuadrat sempurna yang mungkin lebih kecil dari itu (ada ~ sqrt (n) dari mereka). Namun, ini adalah kompleksitas runtime pseudo-polinomial karena runtime sebenarnya menskala secara eksponensial dengan kaitannya dengan ukuran input dalam biner (# bit yang digunakan untuk mewakili angka).

Adakah yang bisa memikirkan algoritma polinomial untuk memecahkan masalah ini? Jika tidak, mungkinkah NP-Complete? Mengapa?

complexity-theory time-complexity np-complete dynamic-programming pseudo-polynomial Martin Copes
sumber
1
Karena penasaran, mengapa Anda secara khusus menanyakan apakah NP-complete? (Secara pribadi, saya akan menduga bahwa itu bahkan tidak di NP, meskipun saya benar-benar tidak tahu.)
ruakh
@ruakh Saya baru-baru ini mengalami masalah ini selama wawancara pengkodean dan mengusulkan solusi pseudo-polinomial menggunakan pemrograman dinamis yang saya jelaskan. Namun, setelah memikirkan masalah itu dengan hati-hati, saya tidak dapat menemukan algoritma waktu polinomial. Saya segera mulai mempertanyakan diri saya sendiri apakah ini sebenarnya bukan masalah NP (-Lengkap).
Martin Copes
Sudahkah Anda mencoba menghitung posisi mana yang menang dan yang kalah? Mungkin suatu pola akan muncul.
Yuval Filmus
@YuvalFilmus Menurut Wikipedia tidak ada rumus yang diketahui untuk pola ini (urutan A030193 dalam OEIS)
Martin Copes
Benar, saya hanya akan mengirim jawaban dengan informasi ini. Lihat juga A224839.
Yuval Filmus

Jawaban:

6

Urutan posisi yang hilang dapat ditemukan di OEIS, A030193 , seperti urutan posisi yang memiliki nilai Grundy 1, A224839 . Ensiklopedia tersebut mengutip beberapa artikel yang relevan. Mungkin beberapa dari mereka membahas algoritma non-sepele untuk menghitung urutannya.

Yuval Filmus
sumber
Seperti yang Anda sebutkan, urutan ini mewakili posisi yang hilang. Bahkan jika Anda dapat memeriksa dalam waktu yang konstan apakah suatu posisi hilang atau tidak (yang tampaknya sulit!) Masalahnya masih meminta Anda untuk mengembalikan langkah optimal, yaitu kuadrat apa yang Anda perlukan untuk mengurangi ke kondisi saat ini untuk sampai ke posisi yang kalah. Masalahnya akan mendidih untuk menemukan posisi yang hilang dengan mengurangi kotak dari kondisi saat ini. Jadi, Anda masih perlu mengulangi semua kotak lebih kecil dari negara, bahkan jika Anda dapat memeriksa apakah suatu posisi hilang dalam waktu yang konstan.
Martin Copes
3
Benar, itu tidak akan cukup, tetapi ini akan menjadi awal yang baik. Mungkin Anda akan mendapatkan beberapa wawasan karena bisa menghitung hanya status kemenangan suatu posisi. Plus, menunjukkan bahwa sulit untuk memutuskan posisi yang hilang akan cukup untuk menunjukkan bahwa masalah Anda sebagaimana dinyatakan NP-hard, dalam versi keputusan yang masuk akal.
Yuval Filmus