Algoritma DNA dan kelengkapan NP

Apa hubungan antara DNA-algoritma dan kelas kompleksitas yang didefinisikan menggunakan mesin Turing? Apa yang diukur oleh kompleksitas seperti waktu dan ruang sesuai dengan algoritma-DNA? Dapatkah mereka digunakan untuk memecahkan contoh masalah NP-lengkap seperti TSP yang tidak dapat diselesaikan oleh mesin von Neumann secara praktis?

Jawaban Soundbite: Komputasi DNA tidak memberikan tongkat ajaib untuk menyelesaikan masalah NP-lengkap, meskipun beberapa peneliti yang dihormati pada 1990-an berpikir untuk sementara waktu mungkin.

Eksperimen komputasi DNA perdana dilakukan di laboratorium yang dipimpin oleh ahli teori angka terkenal Len Adleman. Adleman memecahkan Masalah Travelling Salesman yang kecil - masalah NP-complete yang terkenal, dan dia dan yang lainnya berpikir untuk sementara waktu metode ini mungkin meningkat. Adleman menjelaskan pendekatannya dalam video pendek ini , yang menurut saya menarik. Masalah yang mereka temui adalah untuk memecahkan masalah TSP dengan ukuran sedang, mereka akan membutuhkan lebih banyak DNA daripada ukuran Bumi. Mereka telah menemukan cara untuk menghemat waktu dengan meningkatkan jumlah pekerjaan yang dilakukan secara paralel, tetapi ini tidak berarti masalah TSP membutuhkan kurang dari sumber daya eksponensial untuk menyelesaikannya. Mereka hanya menggeser biaya eksponensial dari jumlah waktu ke jumlah bahan fisik.

(Ada pertanyaan tambahan: jika Anda memerlukan jumlah mesin eksponensial untuk menyelesaikan masalah, apakah Anda secara otomatis memerlukan jumlah waktu eksponensial, atau setidaknya preprocessing, untuk membangun mesin di tempat pertama? Saya akan meninggalkan masalah itu ke satu sisi.)

Masalah umum ini - mengurangi waktu yang dibutuhkan perhitungan dengan mengorbankan beberapa sumber daya lain - telah muncul berkali-kali dalam model komputasi yang diilhami secara biologis. Halaman Wikipedia tentang komputasi membran (abstraksi sel biologis) mengatakan bahwa tipe tertentu dari sistem membran mampu menyelesaikan masalah NP-complete dalam waktu polinomial. Ini bekerja karena sistem itu memungkinkan untuk menciptakan banyak sub-objek secara eksponensial di dalam keseluruhan membran, dalam waktu polinomial. Nah ... bagaimana jumlah bahan baku eksponensial tiba dari dunia luar masuk melalui membran dengan luas permukaan konstan? Jawaban: tidak dipertimbangkan. Mereka tidak membayar sumber daya yang dibutuhkan oleh perhitungan.

Akhirnya, untuk menanggapi Anthony Labarre, yang terhubung ke sebuah makalah yang menunjukkan AHNEP dapat menyelesaikan masalah NP-lengkap dalam waktu polinomial. Bahkan ada makalah yang menunjukkan AHNEP dapat menyelesaikan 3SAT secara linearwaktu. AHNEP = Menerima Jaringan Hibrida dari Prosesor Evolusi. Prosesor evolusi adalah model yang diilhami oleh DNA, yang intinya memiliki string yang pada setiap langkah dapat diubah dengan substitusi, penghapusan, atau penyisipan (penting). Selanjutnya, sejumlah besar string tersedia di setiap node, dan pada setiap langkah komunikasi, semua node mengirim semua string yang benar ke semua node yang terpasang. Jadi tanpa biaya waktu, dimungkinkan untuk mentransfer jumlah informasi yang eksponensial, dan karena aturan penyisipan, string individu dapat menjadi lebih besar selama proses perhitungan, sehingga merupakan whammy ganda.

Jika Anda tertarik pada pekerjaan terbaru dalam biokomputasi, oleh para peneliti yang berfokus pada perhitungan yang praktis di dunia nyata, saya dapat menawarkan ulasan buku ini yang baru-baru ini saya tulis untuk SIGACT News, yang menyentuh secara singkat beberapa bidang.

Ini sangat tergantung pada model Anda.

Pada kenyataannya, komputasi DNA mengikuti hukum-hukum fisika (non-relativistik), dan dengan demikian dapat disimulasikan pada komputer kuantum. Jadi yang terbaik yang bisa Anda harapkan adalah bisa menyelesaikan masalah BQP-lengkap. Namun ini sebenarnya sangat tidak mungkin benar (DNA cukup besar, dan koherensi tidak benar-benar menjadi masalah), dan dengan simulasi hampir pasti P. Penting untuk dicatat, namun, ini adalah efisiensi dalam hal dari jumlah atom yang digunakan, dan terus terang atom cukup murah sehingga jumlah ini adalah astronomi membuat simulasi praktis tabung reaksi yang penuh dengan DNA jauh di luar bidang yang saat ini dimungkinkan.

Akibatnya, banyak orang memilih untuk bekerja dengan model yang memperkirakan apa yang terjadi dengan cukup baik dalam praktiknya, tetapi pecah ketika didorong ke ekstrem. Salah satu contohnya adalah model ubin abstrak, yang ternyata adalah NEXP-complete (lihat makalah Gottesman dan Irani dari FOCS tahun lalu).

Ini adalah jawaban parsial

Dari artikel Wikipedia yang Anda sebutkan, algoritma komputasi DNA Molekul yang menyelesaikan masalah NP-complete tidak membuktikan bahwa masalah NP-complete dapat dipecahkan dalam waktu polinomial pada mesin sekuensial (dengan asumsi layak dalam praktik berarti waktu polinomial). Komputasi DNA dapat dianggap sebagai bentuk komputasi paralel. Akhirnya, dari sudut pandang teori komputabilitas, komputasi DNA tidak lebih kuat dari mesin Turing.

Makalah ini mungkin menarik bagi Anda - kebetulan, saya akan berterima kasih jika seseorang dapat mengklarifikasi pernyataan mengejutkan yang merupakan judulnya.