Buktikan bahwa fungsi boolean yang dapat dihitung dalam T (n) oleh mesin RAM ada di DTIME (T (n) ^ 2)

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 . $f$ $T(n)$ $T$ $\mathrm{DTIME}(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 . $\mathrm{DTIME}(T(n)^3)$ $O(T(n)^2)$ $O(T(n))$ $O(T(n))$

Bagaimana Anda tahu batasan ukuran alamat? Tidak bisakah tulisan pertama saya menjadi ? Dan jika Anda dapat mengikatnya ke , maka ukuran alamat adalah , bukan .

2^{2^{T (n)}}

$2^{2^{T(n)}}$

T (n)

$T(n)$

\log (T (n))

$\log\left(T(n)\right)$

T (n)

$T(n)$

Xodarap

Karena alamat harus ditulis dalam rekaman dengan -Turing Mesin waktu, ukuran (yaitu panjang string) dari alamat tidak boleh melebihi , ruang alamat yang dapat diakses adalah .

T (n)

$T(n)$

O (T (n))

$O(T(n))$

O (2^{T (n)})

$O(2^{T(n)})$

Perhatikan bahwa Arora dan Barak secara eksplisit bertanya dalam pengantar mereka untuk orang lain yang tidak memposting jawaban untuk pertanyaan mereka. Lihat juga kebijakan tentang pertanyaan pekerjaan rumah .

Kaveh

Maaf untuk itu. Saya hanya mempelajari buku itu sendiri dan merasa terganggu dalam pertanyaan itu. Saya tidak tahu apakah simulasi

benar-benar ada atau hanya salah ketik. Jika Anda tahu jawabannya, silakan email saya secara pribadi ke [email protected], dan kemudian saya akan menutup pertanyaan.

O (T (n)^{2})

$O(T(n)^2)$

Anda dapat menemukan lebih banyak di bab pertama buku pegangan ilmu komputer teoretis.

Kaveh

Anda menulis di komentar :

Karena alamat harus ditulis dalam rekaman dengan -Turing Mesin waktu, ukuran (yaitu panjang string) dari alamat tidak boleh melebihi . $T(n)$ $O(T(n))$

Bisakah Anda menggunakan argumen serupa untuk meningkatkan batasan

Kaset [bisa] berukuran dengan pasangan sementara alamat masing-masing pasangan bisa berukuran . $O(T(n)^2)$ $O(T(n))$ $O(T(n))$

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.

Raphael
sumber

Saya harap petunjuk ini cukup samar untuk menghormati keinginan penulis buku tetapi juga agak membantu. (Heuristik: Saya akan memberi tahu seorang siswa lebih banyak jika masalahnya diberikan sebagai latihan. Namun, mungkin tidak dalam ujian.)

Raphael

Buktikan bahwa fungsi boolean yang dapat dihitung dalam T (n) oleh mesin RAM ada di DTIME (T (n) ^ 2)

Jawaban: