Menyusul dari pertanyaan sebelumnya , apa batas bawah ruang terbaik saat ini untuk SAT? Dengan batas bawah ruang yang saya maksud di sini adalah jumlah sel worktape yang digunakan oleh mesin Turing yang menggunakan alfabet biner worktape. Istilah aditif konstan tidak dapat dihindari karena TM...
Sudah diketahui bahwa palindrom dapat dikenali dalam waktu linier pada mesin Turing pita, tetapi tidak pada mesin Turing pita tunggal (dalam hal ini waktu yang dibutuhkan adalah kuadratik). Algoritma linear-waktu menggunakan salinan input, dan dengan demikian juga menggunakan ruang...
Saya mencari makalah survei atau buku yang membahas hasil tentang kompleksitas ruang dari operasi aljabar linear umum seperti peringkat matriks, perhitungan nilai eigen, dll. Saya menekankan bagian "kompleksitas ruang" yang berarti kompleksitas ruang kerja, daripada kompleksitas waktu karena itu...
Teorema Savitch menunjukkan bahwa untuk semua fungsi yang cukup besar , dan membuktikan bahwa ini ketat telah menjadi masalah terbuka selama beberapa dekade. .fNSPACE(f(n))⊆DSPACE(f(n)2)NSPACE(f(n))⊆DSPACE(f(n)2)\mathrm{NSPACE}(f(n)) \subseteq \mathrm{DSPACE}(f(n)^2)fff Misalkan kita mendekati...
Saya telah melakukan beberapa pencarian tentang hal ini tetapi saya tidak dapat menemukan jawaban. Huck menjawabnya sepenuhnya. Terima kasih
Dalam makalah mereka Perkiraan Jarak Orakel , Thorup dan Zwick menunjukkan bahwa untuk setiap grafik tanpa arahan tertimbang, adalah mungkin untuk membangun struktur data ukuran yang dapat mengembalikan ( 2 k - 1 ) -approximate jarak antara setiap pasangan simpul dalam grafik.O ( k n1 + 1 /...
Pertanyaan Umum Apakah teorema hierarki ruang menggeneralisasi ke perhitungan yang tidak seragam? Berikut beberapa pertanyaan spesifik: Apakah ?L/poly⊊PSPACE/polyL/poly⊊PSPACE/polyL/poly \subsetneq PSPACE/poly Untuk semua fungsi pembangun ruang f(n)f(n)f(n) , apakah
Elberfeld, Jakoby, dan Tantau 2010 ( ECCC TR10-062 ) membuktikan versi teorema Bodlaender yang hemat ruang. Mereka menunjukkan bahwa untuk grafik dengan treewidth paling banyak , dekomposisi pohon dengan lebar dapat ditemukan menggunakan ruang logaritmik. Faktor konstan dalam batas ruang tergantung...
Dalam makalah Savitch 1969, "Hubungan Antara Nondeterministik dan Kompleksitas Pita Deterministik", ia menyatakan bahwa "semua fungsi penyimpanan umum L (n)> = lg n dapat diukur. Khususnya, setiap polinomial dalam n dan lg n dapat diukur." Definisinya yang dapat diukur adalah: "Suatu fungsi L...
Trik yang terkenal untuk menyimpan vektor bit menggunakan memori yang tidak diinisialisasi dapat mengalokasikan sedikit vektor ukuran di mana semua bit diatur ke 0 dengan mengalokasikan ( 2 n + 1 ) ⌈ lg n ⌉ bit memori dan menginisialisasi hanya ⌈ lg n ⌉ dari mereka. Representasi ini mendukung...
Dalam film Inception Cobb meminta Ariadne untuk merancang labirin yang membutuhkan waktu dua kali lebih banyak untuk merancang. Ini cocok untuk masalah umum di mana kita memiliki situasi di mana kita terbatas sumber daya dengan jumlah tertentu dan siapa pun yang akan memverifikasi bahwa masalah...
Pertimbangkan masalah keputusan berikut. Biarkan dan biarkan (C_0 ^ n, C_1 ^ n, \ dots, C_ {q-1} ^ n) menjadi cocok enumerasi himpunan bagian dari \ {0,1, \ dots, n-1 \} yang memiliki paling banyak n / 4 elemen.q=∑n/4i=0(ni)q=∑i=0n/4(ni)q = \sum_{i=0}^{n/4}