Sambil berpikir tentang kerumitan pengujian isomorfisme dari grafik asimetris (lihat pertanyaan terkait saya tentang teori), pertanyaan pelengkap muncul di benak saya. Misalkan kita memiliki waktu polinomial mesin Turing MMM yang pada input 1n1n1^n menghasilkan grafik GM,nGM,nG_{M,n} dengan nnn...
Dalam Komputasi Quantum dan Informasi Quantum oleh Nielsen dan Chuang, mereka mengatakan bahwa banyak algoritma yang didasarkan pada transformasi Fourier kuantum bergantung pada properti Coset Invariance dari transformasi Fourier dan menunjukkan bahwa properti invarian dari transformasi lain...
Saya sudah memikirkan masalah ini sejak lama, tetapi tidak tahu. Algoritma pembangkitnya adalah sebagai berikut. Kami berasumsi ada nnn diskrit bernomor dari 000 hingga n−1n−1n - 1 . Kemudian untuk setiap iii di {1,…,n−1}{1,…,n−1}\{1, \dotsc, n - 1\} , kita menjadikan orang tua simpul ke- iii di...
Apa kompleksitas yang paling dikenal untuk menghitung jarak edit yang tepat antara dua string dengan panjang yang sama menggunakan ruang kerja yang sublinear dalam ukuran input? Saya berasumsi input disimpan dalam beberapa format read-only. Apakah ini masalah yang dipelajari sebelumnya? Untuk...
Baru-baru ini, Dana Scott mengusulkan kalkulus lambda stokastik, sebuah upaya untuk memasukkan unsur-unsur probabilistik ke dalam kalkulus lambda (tidak diketik) berdasarkan semantik yang disebut model grafik. Anda dapat menemukan slide-slide-nya secara online misalnya di sini dan makalahnya di...
Wikipedia terdaftar empat masalah yang berada di tapi menduga berada di luarBQPBQPBQP : Integer faktorisasi; Logaritma diskrit; Simulasi sistem kuantum; Menghitung polinomial Jones pada akar persatuan tertentu.PPP Apakah ada masalah lain seperti
Pertanyaan Utama / Umum Biarkan menjadi bahasa. Tentukan bahasa dengan dan untuk . Pertimbangkan . Jadi, kami berulang kali "menyematkan" ke dalam dirinya sendiri untuk memperoleh .LLLLiLiL_iL0=LL0=LL_0 = LLi={xwy:xy∈Li−1,w∈L}Li={xwy:xy∈Li−1,w∈L}L_i = \{xwy : xy \in L_{i-1}, w \in L\}L = ⋃ L i...
USTCONN adalah masalah yang mengharuskan memutuskan apakah ada jalur dari titik sumber sss ke titik target ttt dalam grafik GGG , di mana semua ini diberikan sebagai bagian dari input. Omer Reingold menunjukkan bahwa USTCONN berada di L (doi: 10.1145 / 1391289.1391291 ). Buktinya membangun...
Saat ini, perhitungan real dalam sebagian besar bahasa populer masih dilakukan melalui operasi floating point. Di sisi lain, teori-teori seperti tipe dua efektifitas (TTE) dan teori domain telah lama menjanjikan perhitungan real yang tepat. Jelas, masalah presisi floating point tidak berkurang...
Dalam makalahnya tahun 1995, Algoritma Polinomial-Waktu untuk Faktorisasi Utama dan Logaritma Terpisah pada Komputer Quantum , Peter W. Shor membahas peningkatan pada bagian pencarian-urutan dari algoritma faktorisasi-nya. Output algoritma standar r′r′r' , pembagi dari urutan rrr dari xxx modulo...
Saya ingin memberikan ceramah matematika tentang sistem kontrol revisi git . Sekarang ini banyak digunakan dalam matematika serta industri ilmu komputer. Sebagai contoh, komunitas HoTT (Homotopy Type Theory) menggunakannya, dan itu adalah sistem go to untuk pengeditan kolaboratif dari file teks,...
Masalah keputusan CNF-SAT dapat digambarkan sebagai berikut: Input: Rumus boolean ϕϕ\phi dalam bentuk normal konjungtif. Pertanyaan: Apakah ada tugas variabel yang memenuhi ?ϕϕ\phi Saya sedang mempertimbangkan beberapa pendekatan berbeda untuk memecahkan CNF-SAT dengan mesin Turing dua-tape...
Biarkan menjadi fungsi bernilai integer sehingga ada di . Apakah itu berarti ada di ? Adakah alasan untuk meyakini hal ini tidak mungkin selalu berlaku? Adakah referensi yang harus saya ketahui?2 F # P F # PFFF2 F2F2F# P#P\#PFFF# P#P\#P Agak mengherankan, situasi ini muncul (dengan konstanta yang...
Di bawah ini, MSO menunjukkan logika urutan kedua monadik dari grafik dengan kuantifikasi himpunan sudut dan himpunan tepi. Biarkan menjadi kelompok kecil grafik tertutup. Ini mengikuti dari teori minor minor Robertson dan Seymour bahwa ditandai dengan daftar berhingga dari anak di bawah umur...
Sudah diketahui bahwa masalah kesetaraan tidak dapat diputuskan untuk bahasa bebas konteks umum. Namun, semua bukti dari fakta ini yang saya sadari tampaknya melibatkan beberapa tata bahasa bebas konteks yang ambigu. Untuk alasan ini, saya ingin bertanya apakah diketahui apakah masalahnya tetap...
Saya seorang mahasiswa PhD yang bekerja di bidang ilmu komputer teoretis. Saya telah membaca makalah penelitian dari banyak peneliti dan saya telah melihat banyak alat dan matematika yang mereka gunakan untuk merancang suatu algoritma. Sebagai contoh, lihat makalah penelitian ini [Primality in P] ....
Pierce (2002) memperkenalkan relasi pengetikan di halaman 92 dengan menulis: Relasi pengetikan untuk ekspresi aritmatika, yang dituliskan "t: T", didefinisikan oleh seperangkat aturan inferensi yang menetapkan jenis ke istilah dan catatan kaki mengatakan Simbol sering digunakan sebagai ganti:....
Parity-P adalah seperangkat bahasa yang dikenali oleh mesin Turing non-deterministik yang hanya dapat membedakan antara jumlah genap atau ganjil dari jalur "penerimaan" (daripada jumlah jalur penerimaan yang nol atau tidak nol). Dengan demikian Parity-P pada dasarnya adalah adik kandung PP kerdil:...
Tentukan kompleksitas Gaussian dari matriks menjadi jumlah minimum operasi baris dan kolom elementer yang diperlukan untuk membawa matriks ke dalam bentuk segitiga atas. Ini adalah jumlah antara dan (melalui eleminasi Gaussian). Gagasan ini masuk akal di bidang apa pun.n × nn×nn \times...
Saya tertarik pada masalah berikut: Diberikan satu set X dan himpunan bagian X_1, ..., X_n dari X, temukan pewarnaan elemen-elemen X dengan k warna sehingga elemen-elemen di setiap X_i semuanya berwarna berbeda. Lebih khusus, saya melihat kasus di mana semua X_i berukuran k. Apakah ini dikenal...