Saya telah mendengar dari beberapa peneliti senior dalam ilmu komputer teoretis bahwa bekerja di pekerjaan industri non-penelitian, bahkan hanya selama beberapa tahun, akan membunuh karier Anda sebagai peneliti TCS. Namun saya curiga terhadap klaim bahwa jalan dari menjadi peneliti TCS ke...
Kami mendefinisikan bahasa pohon biasa seperti dalam buku TATA : Ini adalah kumpulan pohon yang diterima oleh otomat pohon terbatas non-deterministik (Bab 1) atau, setara, serangkaian pohon yang dihasilkan oleh tata bahasa pohon biasa (Bab 2). Kedua formalisme memiliki kemiripan yang erat dengan...
Para editor bijak lain di Wikipedia telah menolak permintaan saya untuk memindahkan artikel Wikipedia tentang algoritma Rabin-Karp ke apa yang saya pikir seharusnya disebut, algoritma Karp-Rabin, dengan dasar bahwa nama Rabin-Karp lebih sering digunakan ( salah, jika seseorang menggunakan nomor...
Beberapa masalah NP-hard yang eksponensial pada grafik umum adalah subeksponensial pada grafik planar karena treewidth paling banyak dan mereka eksponensial dalam treewidth.4.9|V(G)|−−−−−−√4.9|V(G)|4.9 \sqrt{|V(G)|} Pada dasarnya saya tertarik jika ada algoritma subeksponensial untuk PLANAR SAT...
RP adalah kelas masalah yang dapat diputuskan oleh mesin Turing nondeterministik yang berakhir dalam waktu polinomial, tetapi itu juga memungkinkan kesalahan satu sisi. P adalah kelas masalah yang biasa diputuskan oleh mesin Turing deterministik yang berakhir dalam waktu polinomial. P = RP...
Perpotongan dua (minimal) DFA dengan n status dapat dihitung menggunakan O (n 2 ) waktu dan ruang. Ini optimal secara umum, karena DFA (minimal) yang dihasilkan mungkin memiliki n 2 status. Namun, jika DFA minimal yang dihasilkan memiliki status z, di mana z = O (n), dapatkah ia dihitung dalam...
Apakah ada referensi yang membahas hal
Peringkat tanda dari matriks A dengan entri + 1, -1 adalah peringkat paling rendah (di atas real) dari matriks B yang memiliki pola tanda yang sama dengan A (yaitu, untuk semua i , j ). Gagasan ini penting dalam kompleksitas komunikasi dan teori belajar.SEBUAHsaya jBsaya j>
Telah diketahui dengan baik bahwa bukti apa pun yang menyelesaikan pertanyaan P vs NP harus mengatasi relativization , bukti alami dan hambatan algebrization . Diagram berikut ini membagi "ruang bukti" menjadi beberapa wilayah. Sebagai contoh, sesuai dengan set bukti yang merelatifkan dan...
Pertimbangkan pertanyaan ini diselesaikan. Saya tidak akan memilih jawaban terbaik karena mereka semua telah berkontribusi pada pemahaman saya tentang topik ini. Saya tidak yakin manfaat apa yang kita miliki dengan secara formal mendefinisikan semantik logika predikat. Tetapi saya melihat nilai...
Pertimbangkan masalah berikut: diberikan formula CNF dan tugas yang memenuhi formula ini, adakah tugas lain yang memuaskan untuk formula ini? Apa kompleksitas masalah ini? (Ini pasti di NP, tetapi juga NP-keras?) Bagaimana jika Anda tidak diberi tugas dan Anda hanya ingin memutuskan apakah...
Sudahkah kompleksitas masalah berikut dipelajari? Input : grafik kubik (atau reguler) , batas atas alami333G=(V,E)G=(V,E)G=(V,E)ttt Pertanyaan : apakah ada partisi menjadi bagian dari ukuran sehingga jumlah pesanan dari subgraph yang sesuai (belum terhubung) paling banyak
Baru-baru ini saya mengajar ekspander, dan memperkenalkan gagasan grafik Ramanujan. Michael Forbes bertanya mengapa mereka dipanggil seperti ini, dan saya harus mengakui bahwa saya tidak tahu. Siapa
1) Apa, jika ada, hubungan antara pengetikan statis dan tata bahasa formal? 2) Secara khusus, apakah mungkin untuk otomat terikat linier untuk memeriksa apakah, katakanlah, program C ++ atau SML diketik dengan baik? Otomat tumpukan bertumpuk? 3) Apakah ada cara alami untuk mengekspresikan aturan...
Hai teman-teman, saya mengerti bahwa trik padding memungkinkan kita menerjemahkan kelas kompleksitas ke atas - misalnya . Padding berfungsi dengan "menggembungkan" input, menjalankan konversi (katakanlah dari katakanlah ke ), yang menghasilkan algoritma "ajaib" yang dapat Anda jalankan pada input...
Permintaan maaf karena mengajukan pertanyaan yang pastinya ada dalam banyak referensi standar. Saya ingin tahu tentang pertanyaan dalam judul, khususnya saya memikirkan sirkuit Boolean, tidak ada kedalaman yang terikat. Saya menempatkan "terkecil" dalam tanda kutip untuk memungkinkan kemungkinan...
Mengingat hasil terbaru dari Arora, Barak, dan Steurer, Algoritma Subeksponensial untuk Game Unik dan Masalah Terkait , saya tertarik pada masalah grafik yang memiliki algoritma waktu subeksponensial tetapi diyakini tidak dapat dipecahkan secara polinomial. Contoh terkenal adalah grafik isomorfisme...
Biasanya seseorang membuat grafik dan kemudian mengajukan pertanyaan tentang dekomposisi nilai eigen matriks adjacency (atau kerabat dekat seperti Laplacian ) (juga disebut spektra grafik ). Tapi bagaimana dengan masalah sebaliknya? Mengingat nilai eigen, bisa satu (efisien) menemukan grafik yang...
Saya sedang membaca ini . Ia mengatakan ... Anda tidak akan mendapati diri Anda kelaparan karena pendanaan seperti Matematika Murni. (Anda akan selalu menemukan diri Anda kelaparan untuk pendanaan.) ... Mengapa matematikawan murni membutuhkan dana? Mengapa seseorang yang melakukan penelitian...
Apakah algoritme waktu polinomial deterministik yang dikenal untuk masalah berikut: Input: angka alami nnn (dalam pengkodean biner) Output: bilangan prima p>np>np > n . (Menurut daftar masalah terbuka oleh Leonard Adleman, masalahnya terbuka pada 1995.)