Misalkan kita memiliki matriks n oleh n. Apakah mungkin untuk menyusun ulang baris dan kolomnya sehingga kita mendapatkan matriks segitiga-atas? Pertanyaan ini dimotivasi oleh masalah ini: Urutan topologis positif Masalah keputusan awal setidaknya sekeras yang ini, jadi hasil NP-kelengkapan akan...
DFA memiliki kata sinkronisasi jika ada string yang mengirim keadaan DFA ke satu keadaan. Dalam 'The Cerny Conjecture for Aperiodic Automata ”oleh AN Trahtman (Matematika Diskrit dan Ilmu Komputer Teoritis vol. 9: 2, 2007, hal.3-10), ia menulis, Cerny menduga pada tahun 1964 bahwa setiap N-state...
Apa saja masalah kompleksitas komputasi utama dan terbuka yang muncul dari bahasa pemrograman, terutama analisis dan kompilasi program? Saya mencari masalah pada baris "kompleksitas waktu inferensi tipe Hindley-Milner" atau "kompleksitas waktu 0CFA" (meskipun keduanya merupakan masalah yang...
Saya membaca bahwa pemrograman linear integer dapat dipecahkan dalam waktu polinominal jika jumlah variabel diperbaiki, yaitu . Jika jumlah variabel tumbuh secara logaritmik, yaitu untuk input ukuran , apakah masalahnya masih dapat dipecahkan dalam waktu polinominal atau apakah ini merupakan...
Latar Belakang Fungsi di adalah PAC dipelajari dalam waktu quasipolynomial dengan algoritma klasik yang membutuhkan O ( 2 l o g ( n ) O ( d ) ) dipilih secara acak query untuk belajar sirkuit kedalaman d [1]. Jika tidak ada algoritma faktorisasi 2 n o ( 1 ) maka ini adalah optimal [2]. Tentu saja,...
Saya bertanya-tanya bagaimana menemukan ketebalan grafik tidak berarah jarang. Maksud saya jarang . Maksud saya adalah kompleksitas waktu terendah.|E|=O(|V|)|E|=O(|V|)|E|=O(|V|) Saya memikirkan beberapa modifikasi pada algoritma Tarjan untuk grafik tidak berarah, tetapi saya tidak menemukan hasil...
Saya tertarik pada masalah "terdekat" (dan "paling kompleks") dengan dugaan Collatz yang telah berhasil diselesaikan (yang menurut Erdos terkenal "matematika belum matang untuk masalah seperti itu"). Telah terbukti bahwa kelas masalah "Collatz-like" tidak dapat diputuskan. Namun, masalah yang...
Tujuan : Menyelesaikan dugaan bahwa tidak ada bidang proyeksi pesanan 12. Pada tahun 1989, menggunakan pencarian komputer pada sebuah Cray, Lam membuktikan bahwa tidak ada bidang proyektif pesanan 10 ada. Sekarang Angka Tuhan untuk Rubik's Cube telah ditentukan setelah hanya beberapa minggu...
Pertimbangkan beberapa bahasa sedemikian rupa sehingga:LLL L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L∈DTIME(O(f(n)))∩DSPACE(O(g(n)))L \in DTIME(O(f(n))) \cap DSPACE(O(g(n))) dan jadi itu L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L∉DTIME(o(f(n)))∪DSPACE(o(g(n)))L \not\in DTIME(o(f(n))) \cup DSPACE(o(g(n))) Dengan...
Bab 1 buku Metode Probabilistik, oleh Alon dan Spencer menyebutkan masalah berikut: Diberikan grafik , putuskan apakah konektivitas tepinya setidaknya n / 2 atau tidak.GGGn/2n/2n/2 Penulis menyebutkan adanya sebuah algoritma oleh Matula dan meningkatkan ke O ( n 8 / 3 log n )
Diketahui bahwa menentukan apakah triangulasi 3-manifold yang diberikan adalah 3-bola di NP, melalui kerja oleh Saul Schleimer pada tahun 2004: "Pengenalan bola terletak pada NP" arXiv: math / 0407047v1 [math.GT] . Saya bertanya-tanya apakah ini telah ditetapkan untuk melengkapi NP dalam lima atau...
Teori kompiler tampaknya menjadi subjek yang cukup diperiksa. Apa saja masalah terbuka atau penelitian terkini yang terjadi di
Oleh http://www.cs.umd.edu/~jkatz/complexity/relativization.pdf Jika adalah bahasa PSPACE-lengkap, P A = N P A .AAAPA=NPAPA=NPAP^{A}=NP^{A} Jika adalah oracle waktu polinomial deterministik, P B ≠ N P B (dengan asumsi P ≠ N P ).BBBPB≠NPBPB≠NPBP^{B}\ne NP^{B}P≠NPP≠NPP\ne NP adalah kelas masalah...
Apa masalah dengan properti berikut: 1) mereka adalah pembatasan (mungkin diketahui) masalah yang PSPACE-complete; 2) versi terbatasnya ada di PSPACE, tetapi ini merupakan masalah terbuka jika mereka PSPACE-complete (atau bahkan jika mereka NP-hard). Empat contoh dari "puzzle &...
Saya mencari daftar tentang kompleksitas yang diketahui atau tidak diketahui dari berbagai masalah teori / aljabar. Sebagai contoh, GCD di terbuka,NC1NC1NC^1 anjak piutang dalam terbuka,PPP komputasi berkas cohomology yaitu -Hard# P#P\#P , Arora dan Barak menyatakan bahwa varian anjak piutang...
Greibach terkenal didefinisikan bahasa , yang disebut versi non-deterministik dari D 2 , sehingga setiap CFL adalah gambar morphic kebalikan dari H . Apakah ada pernyataan serupa dengan DCFL, mungkin dengan pembatasan morfisme diizinkan?HHHD2D2D_2HHH (Lihat, misalnya, M. Autebert, J. Berstel, dan...
Dalam kompleksitas komunikasi, dugaan log-rank menyatakan hal itu cc(M)=(logrk(M))O(1)cc(M)=(logrk(M))O(1)cc(M) = (\log rk(M))^{O(1)} Di mana adalah kompleksitas komunikasi M ( x , y ) dan r k ( M ) adalah pangkat M (sebagai matriks) atas
Dalam proyek-proyek Polymath, sebuah kelompok besar mengerjakan masalah terbuka. Masalah apa yang tampaknya paling berhasil dalam kerangka kerja ini? Apakah ada kandidat yang baik untuk proyek polymath dalam ilmu komputer teoretis? Adakah kendala yang membuat proyek Polymath lebih kecil...
Kita tahu bahwa . Dari Teorema Savitch, , dan, dari Space Hierarchy Teorem, . Jadi, karena kita tidak tahu apakah , kita tidak tahu apakah , atau kita tahu itu ? Adakah yang mencoba membuktikan bahwa \ mathcal L ^ 2 \ subseteq \ mathcal P ? Apa hasil terbaru, atau upaya, dengan cara ini? Saya sudah...
Background––––––––––––––Background_\underline{\bf Background} Pada tahun 2005, Regev [1] memperkenalkan masalah Learning with Errors (LWE), generalisasi dari Learning Parity with Error error. Asumsi kekerasan masalah ini untuk pilihan parameter tertentu sekarang mendasari bukti keamanan untuk...