Pertanyaannya adalah latihan 1.9 dari buku Arora-Barak's Computational Complexity - A Modern Approach :
Tentukan mesin RAM Turing menjadi mesin Turing yang memiliki memori akses acak. Kami meresmikan ini sebagai berikut: Mesin memiliki array A tak terbatas yang diinisialisasi ke semua kosong. Ini mengakses array ini sebagai berikut. Salah satu kaset kerja mesin ditetapkan sebagai pita alamat. Juga mesin memiliki dua simbol alfabet khusus yang dilambangkan oleh R dan W dan status tambahan yang kami tunjukkan dengan q_access. Setiap kali mesin memasuki q_access, jika pita alamatnya berisi 'i'R (di mana' i 'menunjukkan representasi biner dari i) maka nilai A [i] ditulis dalam sel di sebelah simbol R. Jika rekamannya berisi 'i'Wa (di mana a adalah simbol dalam alfabet mesin) maka A [i] diatur ke nilai a.
Tunjukkan bahwa jika fungsi Boolean dapat dihitung dalam waktu (untuk beberapa waktu dibangun ) oleh RAM TM, maka berada di .T ( n ) T D T I M E ( T ( n ) 2 )
Solusi sepele dengan menggunakan pasangan rekaman rekaman tambahan (alamat, nilai) ternyata berada di , karena rekaman itu bisa berukuran dengan pasangan sementara alamat masing-masing pasangan bisa berukuran .O ( T ( n ) 2 ) O ( T ( n ) ) O ( T ( n ) )
Jawaban:
Anda menulis di komentar :
Bisakah Anda menggunakan argumen serupa untuk meningkatkan batasan
Anda menyebutkan dalam pertanyaan? Anda mungkin perlu mengingat operasi apa yang mungkin dilakukan dalam waktu konstan pada RAM, yang menggunakan definisi tepat yang digunakan penulis.
sumber