Saya ingin mendefinisikan pengertian "kedekatan" antara dua bahasa reguler dari kata-kata terbatas dalam Σ∗Σ∗\Sigma^* (dan / atau kata-kata tak terbatas dalam ). Ide dasarnya adalah bahwa kita ingin dua bahasa menjadi dekat jika mereka tidak berbeda dengan banyak kata. Kami juga dapat menggunakan...
Apa yang diketahui tentang kelas bahasa yang dikenali oleh automata terbatas yang memiliki keadaan awal dan penerima yang sama? Ini adalah bagian yang tepat dari bahasa biasa (karena setiap bahasa tersebut berisi string kosong), tetapi seberapa lemah itu? Apakah ada karakterisasi aljabar...
Diberi matriks A dengan entri rasional. Apa kompleksitas untuk memeriksa A yang dapat didiagonalisasi?n×nn×nn\times nAAAAAA Saya menduga bahwa ini dapat dilakukan dalam P, tetapi saya tidak tahu referensi apa pun. Namun, pertanyaan yang lebih menarik adalah, adakah kelas kompleksitas yang lebih...
Diketahui bahwa banyak masalah logika (misalnya masalah kepuasan beberapa logika modal) tidak dapat ditentukan. Ada juga banyak masalah yang tidak dapat dipastikan dalam teori algoritma, misalnya dalam optimasi kombinatorial. Tetapi dalam prakteknya heuristcs dan perkiraan algoritma bekerja dengan...
Secara informal, fungsi satu arah didefinisikan sehubungan dengan algoritma PTIME. Mereka dapat dihitung dalam waktu polinomial tetapi tidak dapat dibalik dalam waktu polinomial kasus-rata. Keberadaan fungsi tersebut merupakan masalah terbuka yang penting dalam ilmu komputer teoretis. Saya...
Biarkan fff menjadi fungsi Boolean dari variabel Boolean. Misalkan menjadi nilai yang diharapkan dari ketika diperoleh dari dengan membalik setiap koordinat dengan probabilitas .g ( x ) = T ϵ ( f ) ( x ) f ( y ) y x ϵ / 2nnng(x)=Tϵ(f)(x)g(x)=Tϵ(f)(x)g(x)=T_\epsilon (f)
Ingat transformasi passing lanjutan (transformasi CPS) yang membawa AAA ke βA:=RRAβA:=RRA\beta A \mathrel{{:}{=}} R^{R^A} (di mana RRR adalah tetap) dan f:A→Bf:A→Bf : A \to B ke βf:βA→βBβf:βA→βB\beta f : \beta A \to \beta B didefinisikan oleh Sebenarnya kita memilikikelanjutan monaddengan satuan...
Sehubungan dengan pertanyaan ini, terpikir oleh saya untuk bertanya-tanya: apa kompleksitas waktu untuk satu mesin single-head Turing untuk menghitung panjang inputnya? Untuk lebih spesifik, misalkan alfabet tape adalah , inputnya adalah string dalam ( 0 + 1 ) ∗ dikelilingi oleh blank, mesin...
Pertimbangkan masalah berikut. Input: Grafik tidak berarah . Output: Grafik H yang merupakan minor G dengan kepadatan tepi tertinggi di antara semua anak di bawah umur G , yaitu, dengan rasio tertinggi | E ( H ) | / | V ( H ) |
Apakah diketahui jika masalah evaluasi rangkaian ada di ? Bagaimana dengan (uniform )?NC1NC1\mathsf{NC^1}NC1NC1\mathsf{NC^1}ALogTimeALogTime\mathsf{ALogTime}NC1NC1\mathsf{NC^1} Kita tahu bahwa sirkuit dengan kedalaman dapat dievaluasi dengan sirkuit dengan kedalaman mana adalah konstanta...
Apa sebenarnya ilmu komputer teoretis? Apakah ini mempelajari kode dalam berbagai bahasa dan membuat aplikasi di platform? Atau hanya memikirkan algoritma yang lebih cepat dan lebih cepat sehingga Anda dapat mencapai tugas lebih efisien oleh komputer? Atau pemrograman dan pemikiran situasi...
Seperti yang saya pahami, bukti bahwa P = NP atau P ≠ NP harus tidak dapat direlatifikasi (seperti dalam teori rekursi). Namun, pada dasarnya semua bukti tampaknya relativizable. Apa contoh yang baik dari bukti yang tidak dapat direlatifikasi, dari jenis yang perlu P = NP / P ≠ NP bukti, yang...
Beberapa waktu yang lalu, saya memposting permintaan referensi untuk masalah grafik di mana kami ingin menemukan 2-partisi tepi di mana kedua set memenuhi properti yang tidak terkait dengan kardinalitas mereka. Saya mencoba membuktikan bahwa masalah berikut ini NP-hard: Diberikan turnamen ,...
Dalam Bundeswettberweb Infomatik 2010/2011, ada masalah yang menarik: Untuk fix , temukan minimal k dan peta φ : { ( i , j ) | i ≤ j ≤ n } → { 1 , ... , k } , sedemikian sehingga tidak ada tiga ( i , j ) , ( i + l , j ) , ( i + l , j + l ) dengan φ (
Asumsikan P NP.≠≠\ne Teorema Ladner mengatakan bahwa ada masalah NP Menengah (masalah dalam NP yang tidak dalam P atau NP-Lengkap). Saya telah menemukan beberapa referensi terselubung online yang menyarankan (saya pikir) bahwa ada banyak "level" dari bahasa yang saling direduksi dalam NPI yang...
Apakah semua berikut ini dapat bertahan secara bersamaan? LsLsL_s terkandung dalam untuk semua bilangan bulat positif . sLs+1Ls+1L_{s+1}sss L=⋃sLsL=⋃sLsL = \bigcup_s L_s adalah bahasa dari semua kata hingga lebih dari .{0,1}{0,1}\{0,1\} Ada beberapa kelas kompleksitas CCC dan gagasan yang tepat...
Misalkan ada grafik . Saya ingin menguji apakah V dapat dipartisi menjadi dua set disjoint V 1 dan V 2 sehingga subgraph yang diinduksi oleh V 1 dan V 2 adalah grafik satuan interval.G = ( V, E)G=(V,E)G=(V,E)VVVV1V1V_1V2V2V_2V1V1V_1V2V2V_2 Saya tahu tentang NP-kelengkapan penentuan angka interval...
Misalkan Anda bertemu dengan programmer yang telah mengambil beberapa program pemrograman profesional (/ saya pikir sendiri) tetapi tidak belajar matematika tingkat universitas. Untuk menunjukkan kepada mereka keindahan TCS, saya ingin mengumpulkan beberapa hasil bagus / pertanyaan terbuka yang...
Kita diberi grafik asiklik terarah dengan angka yang terkait dengan setiap simpul ( g : V → N ), dan nomor target TG=(V,E)G=(V,E)G=(V,E)g:V→Ng:V→Ng:V\to \mathbb{N} .T∈NT∈NT\in \mathbb{N} The DAG bagian sum masalah (mungkin ada dengan nama yang berbeda, referensi akan menjadi besar) menanyakan...
Sebuah pertanyaan baru-baru ini (lihat Konsekuensi dari NP = PSPACE ) meminta "jahat" konsekuensi dari NP=PSPACENP=PSPACENP=PSPACE . Jawaban daftar beberapa konsekuensi keruntuhan, termasuk NP=coNPNP=coNPNP=coNP dan lain-lain, memberikan banyak alasan untuk percaya NP≠PSPACENP≠PSPACENP\neq PSPACE...