Saya benar-benar ingin bantuan Anda untuk membuktikan hal berikut. Jika maka .P = N P.N T i m e ( n100) ⊆ D T i m e ( n1000)NTsayame(n100)⊆DTsayame(n1000)\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})P = N PP=NP\mathrm{P}=\mathrm{NP} Di sini, adalah kelas semua bahasa yang dapat...
Saya mencoba untuk berpendapat bahwa N bukan NP sama dengan menggunakan teorema hierarki. Ini adalah argumen saya, tetapi ketika saya menunjukkannya kepada guru kami dan setelah deduksi, ia mengatakan bahwa ini bermasalah di mana saya tidak dapat menemukan alasan kuat untuk menerimanya. Kami...
Wikipedia mengatakan penyatuan berdasarkan peringkat tanpa kompresi jalur memberikan kompleksitas waktu diamortisasi O(logn)O(logn)O(\log n) , dan bahwa penyatuan berdasarkan peringkat dan kompresi jalur memberikan kompleksitas waktu diamortisasi O(α(n))O(α(n))O(\alpha(n)) (di mana αα\alpha adalah...
Saya telah mempelajari koefisien korelasi peringkat Spearman ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2−−−−−−−−−−−−−−−−−−−√ρ=∑i(xi−x¯)(yi−y¯)∑i(xi−x¯)2∑i(yi−y¯)2\qquad \displaystyle \rho = \frac{\sum_i(x_i-\bar{x})(y_i-\bar{y})}{\sqrt{\sum_i (x_i-\bar{x})^2 \sum_i(y_i-\bar{y})^2}} . untuk dua daftar...
Pada 1950-an sejumlah metode untuk meminimalkan sirkuit untuk fungsi Boolean telah ditemukan. Apakah ada perluasan dari metode tersebut atau yang serupa untuk mengoptimalkan kompleksitas waktu atau ruang dari algoritma? Misalnya implementasi bubble sort sebagai input untuk algoritma seperti itu...
Ada beberapa HAIOO -Notasi, seperti O ( n )O(n)O(n) atau O ( n2)O(n2)O(n^2) dan seterusnya. Saya bertanya-tanya, apakah ada variasi dari mereka dalam kenyataan seperti O ( 2 n2)O(2n2)O(2n^2) atau O ( logn2)O(logn2)O(\log n^2) , atau apakah itu secara matematis salah. Atau akankah hal yang benar...
Jawaban untuk pertanyaan ini di Crypto Stack Exchange pada dasarnya mengatakan bahwa, untuk mengukur kompleksitas masalah logaritma, kita harus memperhitungkan panjang angka yang mewakili ukuran grup. Tampaknya sewenang-wenang, mengapa kita tidak memilih ukuran kelompok sebagai argumen? Adakah...
Misalkan kita ingin menggabungkan dua relasi dengan predikat. Apakah ini di NC? Saya menyadari bahwa buktinya tidak berada di NC akan menjadi bukti bahwa , jadi saya akan menerima bukti itu menjadi masalah terbuka sebagai jawaban.P≠NCP≠NCP\not=NC Saya tertarik pada kasus umum serta kasus-kasus...
Banyak kelas kompleksitas memiliki masalah "lengkap". Apakah ada masalah lengkap untuk kelas kompleksitas masalah yang dapat diselesaikan dalam waktu ?O ( 1 )O(1)O(1) Suatu komplikasi adalah bahwa kelas ini tergantung pada model perhitungan; masalah dapat dipecahkan dalam waktu dalam satu model...
Jika Anda memiliki algoritma penyortiran cepat, dan Anda selalu memilih elemen terkecil (atau terbesar) sebagai poros Anda; Apakah saya benar dengan asumsi bahwa jika Anda memberikan kumpulan data yang sudah diurutkan, Anda akan selalu mendapatkan kinerja kasus terburuk terlepas dari apakah daftar...
Mari kita ambil contoh reduksi → → 2d 3d: Berapa biaya simulasi robot seluler 3d oleh robot seluler 2d? Berikut adalah beberapa pertanyaan yang lebih spesifik: Algoritma seperti apa yang akan mengubah kompleksitas waktu mereka, seberapa banyak? Apa yang akan menjadi ide dasar untuk pengkodean;...
Seperti yang dinyatakan dalam pertanyaan, bagaimana kita membuktikan bahwa ?NTIME(f(n))⊆DSPACE(f(n))NTIME(f(n))⊆DSPACE(f(n))\textbf{NTIME}(f(n)) \subseteq \textbf{DSPACE}(f(n)) Adakah yang bisa mengarahkan saya ke bukti atau menguraikannya di sini? Terima
Anda menjamu liga basket 1 v 1 dengan jadwal pertandingan. Di akhir liga, Anda meminta setiap pemain untuk melaporkan rekor menang-kalah (tidak ada ikatan), tetapi Anda ingin memeriksa apakah kedudukan yang diusulkan benar-benar dimungkinkan berdasarkan jadwal. Misalnya: Anda memiliki empat pemain...
Apakah masalah berikut telah dipelajari sebelumnya? Jika ya, pendekatan / algoritma apa yang dikembangkan untuk menyelesaikannya? Masalah ("Masalah Ketinggian Penumpukan Maksimum") Diberikan nnnpoligon, temukan susunannya yang stabil dan tidak tumpang tindih yang memaksimalkan ketinggian...
Membiarkan L1L1L_1 dan L2L2L_2 menjadi yang berikut: L1={r:∃x,y∈Z such that x2+y2=r}L1={r:∃x,y∈Z such that x2+y2=r}L_1=\{r:\exists x,y \in \mathbb{Z} \text{ such that } x^2+y^2=r\} L2={(N,M):M<N,∃1<d≤M such that d|N}L2={(N,M):M<N,∃1<d≤M such that d|N}L_2=\{(N,M):...
Andaikata kita memiliki komputer kuantum dengan jumlah qubit yang cukup, dapatkah kita menggunakannya untuk melakukan aljabar linier lebih cepat daripada yang kita dapat dengan komputer klasik? Seperti apa speedup yang bisa kita harapkan? Adakah yang membuat algoritma kuantum untuk aljabar linier,...
Kami baru saja selesai kami "Waktu Konstruksi gedung" pelajaran di kelas minggu lalu, dan kami, demi contoh ini, menunjukkan bahwa sepenuhnya waktu constructible, yaitu terdapat (multi-tape deterministik) mesin Turing bahwa untuk diberikan, berhenti setelah tepat langkah, dan hanya bertanya apakah...
Saya benar-benar ingin bantuan Anda dengan membuktikan atau menyangkal klaim berikut: . Dalam teori kompleksitas komputasi, BPP, yang berarti waktu polinom probabilitas terbatasi-kesalahan adalah kelas masalah keputusan yang dipecahkan oleh mesin Turing probabilistik dalam waktu polinomial, dengan...
Saya seorang sarjana ilmu komputer yang masih muda, dan saya diminta untuk menulis makalah yang melibatkan faktorisasi bilangan bulat. Akibatnya, saya harus melihat algoritma Shor pada komputer kuantum. Untuk algoritma lain, saya dapat menemukan persamaan khusus untuk menghitung jumlah instruksi...
Saya belajar tentang analisis asimptotik, dan telah melihat beberapa kerumitan yang terlihat eksotis yang hidup di antara yang umum lainnya. Misalnya "log log n" adalah antara 1 dan log n. Itu membuat saya bertanya-tanya apakah seseorang dapat selalu menemukan kompleksitas di antara dua...