Pertanyaan yang diberi tag «reference-request»

Referensi-permintaan digunakan ketika penulis perlu tahu tentang pekerjaan yang terkait dengan pertanyaan tersebut.


Buku apa yang harus dibaca semua orang?
[ Garis Waktu ] Pertanyaan ini memiliki semangat yang sama tentang makalah apa yang harus dibaca semua orang dan video apa yang harus ditonton semua orang . Ia meminta buku-buku luar biasa di berbagai bidang ilmu komputer teoretis. Buku-buku itu bisa berorientasi matematika, tetapi Anda mungkin merasa hebat untuk seorang …


Contoh harga abstraksi?
Ilmu komputer teoretis telah memberikan beberapa contoh "harga abstraksi." Dua yang paling menonjol adalah untuk eliminasi Gaussian dan sortasi. Yaitu: Diketahui bahwa eliminasi Gaussian optimal untuk, katakanlah, menghitung determinan jika Anda membatasi operasi pada baris dan kolom secara keseluruhan [1]. Algoritma Strassen jelas tidak mematuhi batasan itu, dan secara asimptotik …

Apa buku TCS terbaru yang konsepnya tersedia online?
Setelah posting Apa Buku Yang Harus Dibaca Semua Orang , saya perhatikan ada buku-buku terbaru yang draftnya tersedia online. Sebagai contoh, entri Algoritma Approximation dari posting di atas mengutip sebuah buku 2011 (belum dipublikasikan) berjudul Desain algoritma pendekatan . Saya pikir mengetahui karya terbaru sangat berguna bagi siapa pun yang …

Makalah terkait TCS lucu dll?
Apa karya terbitan terkait TCS terlucu yang Anda tahu? Harap sertakan hanya yang dimaksudkan untuk menjadi lucu. Karya-karya yang secara eksplisit dibuat untuk menjadi humor cerdas (daripada, katakanlah, kumpulan lelucon singkat tentang teori kompleksitas) lebih disukai. Karya dengan judul lucu (sebenarnya lucu, tidak hanya lucu) juga diterima. Harap hanya satu …

Contoh Matematika “Tidak Terkait” yang Memainkan Peran Mendasar dalam TCS?
Harap sebutkan contoh-contoh di mana teorema dari matematika yang biasanya tidak dianggap berlaku dalam ilmu komputer pertama kali digunakan untuk membuktikan hasil dalam ilmu komputer. Contoh terbaik adalah mereka yang hubungannya tidak jelas, tetapi begitu ditemukan, itu jelas "cara yang tepat" untuk melakukannya. Ini adalah arah yang berlawanan dari pertanyaan …

Apa kompleksitas waktu aktual dari eliminasi Gaussian?
Dalam jawaban untuk pertanyaan sebelumnya , saya menyebutkan kepercayaan umum tetapi salah bahwa eliminasi "Gaussian" berjalan dalam waktu . Meskipun jelas bahwa algoritma ini menggunakan operasi aritmatika , implementasi ceroboh dapat membuat angka dengan banyak bit secara eksponensial. Sebagai contoh sederhana, misalkan kita ingin mendiagonalisasi matriks berikut:O(n3)O(n3)O(n^3)O(n3)O(n3)O(n^3) ⎡⎣⎢⎢⎢⎢⎢⎢⎢211⋮1021⋮1002⋮1⋯⋯⋯⋱⋯000⋮2⎤⎦⎥⎥⎥⎥⎥⎥⎥[200⋯0120⋯0112⋯0⋮⋮⋮⋱⋮111⋯2]\begin{bmatrix} 2 & …



Aplikasi topologi untuk ilmu komputer
Saya ingin menulis survei tentang aplikasi Topologi dalam Ilmu Komputer. Saya berencana untuk membahas sejarah ide-ide topologi dalam Ilmu Komputer dan juga menyoroti beberapa perkembangan saat ini. Akan sangat membantu jika ada yang bisa memberi masukan tentang pertanyaan di bawah ini. Adakah tulisan atau catatan yang menggambarkan kronologi penggunaan topologi …

Aplikasi TCS untuk matematika klasik?
Kami di TCS sering menggunakan hasil dan gagasan yang kuat dari matematika klasik (aljabar, topologi, analisis, geometri, dll.). Apa saja contoh ketika itu telah terjadi sebaliknya? Berikut adalah beberapa yang saya ketahui (dan juga untuk memberikan rasa dari jenis hasil yang saya tanyakan): Busa kubik (Guy Kindler, Ryan O'Donnell, Anup …

Bisakah satu memperkuat P = NP di luar P = PH?
Dalam Kompleksitas Deskriptif , Immerman memiliki Konsekuensi 7.23. Kondisi berikut ini setara: 1. P = NP. 2. Struktur yang terbatas, terurut, FO (LFP) = SO. Ini dapat dianggap sebagai "memperkuat" P = NP untuk pernyataan yang setara atas (mungkin) kelas kompleksitas yang lebih besar. Perhatikan bahwa SO menangkap polinomial-time hierarki …

Untuk masalah dalam P apakah lebih mudah untuk memverifikasi hasil daripada menemukannya?
Untuk (versi pencarian) dari masalah NP- lengkap, verifikasi suatu solusi jelas lebih mudah daripada menemukannya, karena verifikasi dapat dilakukan dalam waktu polinomial, sementara menemukan saksi membutuhkan waktu (mungkin) eksponensial. Dalam P , bagaimanapun, solusinya juga dapat ditemukan dalam waktu polinomial, sehingga tidak tampak jelas kapan verifikasi lebih cepat daripada menemukan …

Teorema Ladner Umum
Teorema Ladner menyatakan bahwa jika P ≠ NP, maka ada hierarki tak terbatas dari kelas kompleksitas yang secara ketat berisi P dan secara ketat terkandung dalam NP. Buktinya menggunakan kelengkapan SAT di bawah banyak-satu pengurangan NP. Hirarki berisi kelas kompleksitas yang dibangun oleh semacam diagonalisasi, masing-masing berisi beberapa bahasa yang …

Dengan menggunakan situs kami, Anda mengakui telah membaca dan memahami Kebijakan Cookie dan Kebijakan Privasi kami.
Licensed under cc by-sa 3.0 with attribution required.