Apa konsekuensi dari pernyataan bahwa Mesin Turing non-deterministik dapat menyelesaikan NP dalam waktu polinomial?

hari ini saya telah mempelajari tentang masalah NP, kompleksitas komputasi dan teori. Saya yakin saya akhirnya memahami konsep Mesin Turing, namun saya memiliki beberapa keraguan.

Saya dapat menerima bahwa mesin turing non-deterministik memiliki beberapa opsi tentang apa yang harus dilakukan untuk keadaan dan simbol tertentu yang sedang dibaca dan akan selalu memilih opsi terbaik, seperti yang dinyatakan oleh wikipedia

Bagaimana NTM “mengetahui” tindakan mana yang harus diambil? Ada dua cara untuk melihatnya. Salah satunya adalah mengatakan bahwa mesin adalah “penebak yang paling beruntung”; ia selalu memilih transisi yang pada akhirnya mengarah pada keadaan menerima, jika memang ada transisi seperti itu. Cara lainnya adalah dengan membayangkan bahwa mesin tersebut "bercabang" menjadi banyak salinan, yang masing-masing mengikuti salah satu kemungkinan transisi. Sedangkan DTM memiliki satu "jalur komputasi" yang diikutinya, NTM memiliki "pohon komputasi". Jika ada cabang pohon yang berhenti dengan kondisi "terima", kita katakan bahwa NTM menerima masukan.

Apa yang saya tidak mengerti adalah, karena ini adalah mesin imajiner, apa yang kita peroleh dengan mengatakan bahwa mesin ini dapat menyelesaikan masalah NP dalam waktu polinomial? Maksud saya, saya juga bisa berteori tentang mesin ajaib yang memecahkan masalah NP di O(1), apa yang saya peroleh dari itu jika mesin itu tidak pernah ada?

Terima kasih sebelumnya.


complexity-theory theory turing-machines
person Clash    schedule 14.09.2010    source sumber
comment
Itu ide lama. Ini disebut Mesin Oracle.   -  person Yuval Adam    schedule 15.09.2010

Jawaban (6)


arrow_upward
15
arrow_downward

Mesin Turing non-deterministik adalah konsep yang sulit untuk dipahami. Cobalah beberapa sudut pandang lain:

  1. Daripada menjalankan mesin Turing ajaib yang bisa menebak dengan paling beruntung, jalankan mesin meta yang lebih ajaib lagi yang menyiapkan mesin Turing independen yang dapat menebak secara acak dalam jumlah tak terbatas di alam semesta paralel. Setiap kemungkinan rangkaian tebakan dibuat di suatu alam semesta. Jika setidaknya di salah satu alam semesta mesin berhenti dan menerima masukan, itu sudah cukup: contoh masalah diterima oleh mesin meta yang mengatur alam semesta paralel ini. Jika di semua alam semesta mesin menolak atau gagal menghentikan, mesin meta akan menolak kejadian tersebut.

  2. Daripada menebak-nebak atau bercabang-cabang, pikirkan tentang seseorang yang mencoba meyakinkan orang lain bahwa contoh tersebut harus diterima. Orang pertama memberikan serangkaian pilihan yang harus dibuat oleh mesin Turing non-deterministik, dan orang kedua memeriksa apakah mesin menerima masukan dengan pilihan tersebut. Jika ya, orang kedua yakin; jika tidak, orang pertama telah gagal (yang mungkin disebabkan karena contoh tersebut tidak dapat diterima dengan rangkaian pilihan apa pun, atau karena orang pertama memilih rangkaian pilihan yang buruk).

  3. #P4#
    #P5#
    #P6#
    #P7#
    #P8#
    #P9#
    #P10#

Anda juga berkata

Saya juga bisa berteori tentang mesin ajaib yang memecahkan masalah NP di O(1)

Ya kamu bisa. Ini disebut mesin Oracle (tidak ada hubungannya dengan DBMS) dan telah memberikan hasil yang menarik dalam teori kompleksitas . Misalnya, teorema BakerGillSolovay menyatakan bahwa terdapat oracle A dan B sehingga untuk mesin Turing yang memiliki akses ke A, P=NP, tetapi untuk mesin Turing yang memiliki akses ke B, PNP. (A adalah ramalan yang sangat kuat yang membuat non-determinisme menjadi tidak relevan; definisi B agak rumit dan melibatkan trik diagonalisasi.) Ini adalah semacam hasil meta: bukti apa pun yang menyelesaikan pertanyaan P vs NP harus sensitif cukup untuk definisi mesin Turing yang gagal saat Anda menambahkan beberapa jenis oracle.

Nilai dari mesin Turing non-deterministik adalah bahwa mereka menawarkan karakterisasi komputasi yang relatif sederhana dari kelas kompleksitas NP (dan lainnya): alih-alih pohon komputasi atau rumus logika orde kedua, Anda dapat memikirkan komputer yang hampir biasa yang memiliki telah (relatif) sedikit dimodifikasi sehingga dapat membuat tebakan yang sempurna.

person Jouni K. Seppänen    schedule 03.10.2010
comment
+1. Saya belum pernah mendengar teorema oracle itu -- kedengarannya luar biasa. - person Edmund; 03.10.2010

arrow_upward
4
arrow_downward

Apa yang Anda peroleh dari hal ini adalah Anda dapat membuktikan bahwa suatu masalah ada di NP dengan membuktikan bahwa masalah tersebut dapat diselesaikan dengan NTM dalam waktu polinomial.

Dengan kata lain Anda dapat menggunakan NTM untuk mengetahui apakah suatu masalah ada di NP atau tidak.

person sepp2k    schedule 14.09.2010
comment
Bisakah Anda menjelaskannya lebih lanjut? Bagaimana saya bisa membuktikan hal seperti itu menggunakan NTM? - person Clash; 15.09.2010
comment
@Clash: Anda membuat NTM yang memecahkan masalah. Kemudian Anda membuktikan bahwa itu benar dan berjalan dalam waktu polinomial. - person sepp2k; 15.09.2010
comment
Bisakah Anda memposting contoh, tautan untuk mempelajari hal seperti itu? Saya benar-benar bingung bagaimana melakukan itu. Saya tidak terbiasa berpikir non-deterministik. Terima kasih! - person Clash; 15.09.2010
comment
@Clash: misalnya, Anda dapat mengetahui apakah suatu grafik memiliki tiga warna dengan menebaknya secara non-determistik. Untuk |V| putaran pertama, Anda menetapkan warna pada simpul, dan kemudian memeriksa apakah pewarnaan Anda sudah benar. Lihat soal NP-complete untuk contoh lebih lanjut. - person sdcvvc; 15.09.2010
comment
Terima kasih sdwc, akan kita lihat! - person Clash; 15.09.2010

arrow_upward
1
arrow_downward

Menurut definisi, NP adalah singkatan dari waktu polinomial nondeterministik seperti yang dapat dilihat di Wikipedia.

Inkarnasi mesin Turing nondeterministik yang secara acak memilih dan memeriksa (atau merakit) solusi potensial berikutnya akan menyelesaikan masalah NP dalam waktu polinomial dengan beberapa probabilitas (ini akan menyelesaikan masalah dalam waktu poli dengan kepastian mutlak jika itu adalah "yang paling beruntung" penebak").

Oleh karena itu, mengatakan bahwa NTM dapat menyelesaikan masalah dalam waktu polinomial secara efektif berarti bahwa masalah tersebut ada di NP. Sekali lagi ini setara dengan definisi kelas masalah NP.

person Arc    schedule 14.09.2010
comment
Terima kasih sudah menjelaskan, tetapi Anda masih belum menjawab pertanyaan saya... jika tebakan keberuntungan seperti itu tidak ada, mengapa ini berguna... itu seperti mengatakan, hei, jika saya bisa mengetahui hasil lotere sebelumnya kebetulan aku akan kaya. NTM harus bermanfaat untuk hal lain. Inilah yang saya tidak mengerti. - person Clash; 15.09.2010
comment
Komputer kuantum diharapkan (dengan beberapa keterbatasan) mampu menguji semua jalur solusi potensial secara bersamaan dan oleh karena itu berperilaku seperti penebak NTM yang paling beruntung. Komputer kuantum melakukan komputasi dengan qubit, yang setiap kumpulan qubit mewakili kumpulan semua kemungkinan kombinasi jumlah bit konvensional yang sama (superposisi). (Peter) Algoritme Shor untuk memfaktorkan angka / memecahkan enkripsi RSA mengeksploitasi ini. - person Arc; 15.09.2010
comment
Bagian tersulit dari komputer kuantum adalah melindungi superposisi dari dekoherensi (di mana qubit berubah menjadi bit konvensional melalui interaksi fisik dengan dunia) dan pada akhirnya mengekstraksi solusi yang tepat melalui dekoherensi. - person Arc; 15.09.2010

arrow_upward
0
arrow_downward

Saya pikir jawaban Anda ada di pertanyaan Anda. Dengan kata lain, suatu permasalahan dapat dibuktikan bahwa permasalahan tersebut merupakan permasalahan NP jika dapat ditemukan NTM yang dapat menyelesaikan permasalahan tersebut.

Masalah NP adalah masalah kelas khusus, dan NTM hanyalah alat untuk memeriksa apakah masalah yang diberikan termasuk dalam kelas tersebut atau tidak.

Perhatikan bahwa NTM bukanlah mesin tertentu - ini adalah seluruh kelas mesin dengan aturan yang jelas tentang apa yang bisa dan tidak bisa mereka lakukan. Untuk menggunakan mesin "ajaib", Anda perlu mendefinisikannya, dan menunjukkan kelas kompleksitas masalah yang sesuai dengan mesin tersebut.

Lihat http://en.wikipedia.org/wiki/Computational_complexity_theory#Complexity_classes untuk mengetahui lebih lanjut info.

person DanJ    schedule 14.09.2010
comment
Kalau NP juga bisa diartikan sebagai permasalahan yang bisa DIVERIFIKASI secara polytime dengan TM, kenapa saya perlu NTM, padahal itu tidak ada? Terima kasih - person Clash; 15.09.2010
comment
memverifikasi solusi dalam politime dengan TM setara dengan menyelesaikan dalam politime dengan NTM. en.wikipedia.org/wiki/NP_(complexity)#Verifier-based_definition (lihat Definisi mesin) - person DanJ; 15.09.2010
comment
Terkadang lebih mudah untuk menghasilkan NTM daripada TM, namun untuk membuktikan suatu masalah adalah NP, kedua solusi tersebut valid. - person DanJ; 15.09.2010

arrow_upward
-1
arrow_downward

Dari Wikipedia bahasa Ibrani - "NTM pada dasarnya adalah alat untuk berpikir, dan tidak mungkin untuk mengimplementasikan mesin seperti itu". Anda dapat mengganti istilah "NTM" dengan "Algoritma yang pada setiap langkah mencoba semua langkah yang mungkin" atau "Algoritma yang pada setiap langkah memilih langkah berikutnya yang terbaik".. Dan saya rasa Anda memahami sisanya. NTM hadir hanya untuk membantu kita memvisualisasikan algoritma tersebut. Anda dapat melihat di sini bagaimana hal itu seharusnya membantu Anda memvisualisasikan (pada jawaban Pascal Cuoq).

person Oren A    schedule 14.09.2010
comment
Algoritma yang pada setiap langkah dapat memilih dari sejumlah kemungkinan langkah. Apa pun bisa 'memilih' apa saja. NTM hanyalah penebak yang beruntung yang dapat memilih jalur yang benar di setiap langkahnya. - person OTZ; 15.09.2010
comment
@OTZ: Anda juga dapat menganggapnya seolah-olah mencoba segala kemungkinan (klik tautan yang saya berikan). Kedua definisi tersebut setara. Tapi Anda benar, kata-kata aslinya tidak bagus. Mengubahnya. - person Oren A; 15.09.2010

arrow_upward
-1
arrow_downward

Apa yang kita peroleh adalah jika kita memiliki kekuatan magis untuk menebak langkah yang benar, yang hasilnya selalu benar, kita dapat menyelesaikan masalah NPC di POLYTIME. Tentu saja, kita tidak selalu bisa “menebak” langkah yang tepat. Jadi itu hanya khayalan. Namun, sama seperti bilangan imajiner yang dapat diterapkan pada permasalahan dunia nyata, konsekuensinya juga berguna secara teoritis.

Salah satu aspek positif dalam mengubah masalah awal dengan cara ini adalah kita dapat mengatasinya dari berbagai sudut pandang. Dalam ranah teoretis, hal ini merupakan hal yang baik karena kita memiliki (1) lebih banyak pendekatan yang dapat kita ambil (sehingga lebih banyak makalah) dan (2) lebih banyak alat yang dapat kita gunakan jika pendekatan tersebut dapat diungkapkan dalam bidang lain.

person OTZ    schedule 14.09.2010
comment
Saya selalu menggunakan bilangan imajiner di bidang teknik elektro, bilangan tersebut memiliki kegunaan dan keuntungan nyata. Di sisi lain saya tidak melihat keuntungan apa pun mengatakan bahwa sesuatu dapat diselesaikan secara ajaib dalam waktu yang lama. Hal yang saya cari adalah masalah-masalah dunia nyata yang dapat dibantu oleh NTM. Terima kasih @DanJ, ​​dia berbicara tentang NTM, oleh karena itu diselesaikan dalam waktu politime. - person Clash; 15.09.2010
comment
@Clash Kami tidak dapat menerapkan NTM pada masalah dunia nyata apa pun karena tidak mungkin untuk membuatnya. Salah satu keuntungannya, bacalah paragraf kedua yang baru saja saya tambahkan. - person OTZ; 15.09.2010
comment
@DanJ itu NPC. ada apa dengan sikapmu. - person OTZ; 15.09.2010
comment
Bilangan imajiner juga tidak ada, namun kita tetap menggunakannya dalam banyak situasi. Saya tertarik dengan kasus-kasus di mana NTM berguna untuk apa pun. Saya pikir akhirnya terlintas di kepala saya bahwa NTM berguna untuk membuktikan bahwa suatu masalah adalah NP, sedangkan menggunakan TM deterministik untuk membuktikan hal seperti itu akan lebih sulit, yang saya perlukan sekarang adalah contoh bagaimana saya bisa membuktikan hal tersebut dengan sebuah NTM. Dapatkah Anda memikirkan atau mengetahui tautan ke hal seperti itu? Terima kasih! - person Clash; 15.09.2010