Digunakan untuk pertanyaan tentang bukti yang ada atau kemungkinan dari teorema atau dugaan tertentu
Maaf untuk judul yang menarik. Saya ingin mengerti, apa yang harus dilakukan seseorang untuk menyangkal tesis Gereja-Turing? Di suatu tempat saya membaca secara matematis tidak mungkin untuk melakukannya! Mengapa? Turing, Rosser dll menggunakan istilah yang berbeda untuk membedakan antara: "apa...
Tujuan dari pertanyaan ini adalah untuk mengumpulkan contoh-contoh dari ilmu komputer teoretis di mana penggunaan komputer secara sistematis sangat membantu dalam membangun dugaan yang mengarah pada teorema, memalsukan pendekatan dugaan atau bukti, membangun / memverifikasi (bagian dari)...
Di MathOverflow, Timothy Gowers mengajukan pertanyaan berjudul " Mendemonstrasikan kekakuan itu penting ". Sebagian besar diskusi di sana tentang kasus-kasus yang menunjukkan pentingnya pembuktian, yang mungkin tidak perlu diyakinkan oleh orang-orang di CSTheory. Dalam pengalaman saya bukti perlu...
Ini adalah pertanyaan yang terkait dengan yang ini . Menempatkannya kembali dalam bentuk yang lebih sederhana setelah banyak diskusi di sana, yang rasanya seperti pertanyaan yang sama sekali berbeda. Bukti klasik dari ketidakpastian masalah penghentian tergantung pada menunjukkan kontradiksi...
Bukti standar ikatan Chernoff (dari buku Acak Algoritma ) menggunakan Markov ketidaksetaraan dan fungsi menghasilkan momen, dengan sedikit ekspansi Taylor dilemparkan. Tidak ada yang terlalu sulit, tetapi agak mekanis. Tetapi ada bukti terikat Chernoff lainnya yang mengekspos struktur yang lebih...
Kami tahu bahwa jika Anda memiliki mesin PSPACE, itu cukup kuat untuk memberikan bukti interaktif dari level apa pun hierarki polinomial. (Dan jika saya ingat benar, semua yang Anda butuhkan adalah #P.) Tetapi misalkan Anda ingin memberikan bukti keanggotaan interaktif dalam Σ2Σ2\Sigma_2 bahasa....
Saya (dan masih) sangat tertarik pada jawaban untuk pertanyaan ini, karena ini adalah variasi yang menarik pada kompleksitas permainan yang belum terselesaikan, jadi saya menawarkan hadiah. Saya pikir pertanyaan aslinya kemungkinan besar terlalu sulit, jadi saya memposting tiga pertanyaan terkait...
Saya memiliki minat yang meningkat pada teori grafik spektral, yang menurut saya menarik, dan saya sudah mulai mengumpulkan beberapa dokumen yang belum saya baca lebih teliti daripada yang saya miliki sejauh ini. Namun, saya ingin tahu tentang pernyataan yang muncul di beberapa sumber (misalnya di...
Apakah ada contoh mainan yang memberikan wawasan 'esensial' untuk memahami tiga hambatan yang diketahui untuk masalah - relativization, bukti alami dan algebrization?P=NPP=NPP =
Saya tertarik pada contoh masalah di mana teorema yang tampaknya tidak ada hubungannya dengan mekanika kuantum / informasi (misalnya menyatakan sesuatu tentang benda-benda klasik murni) tetap dapat dibuktikan menggunakan alat kuantum. Sebuah survei Bukti Kuantum untuk Teorema Klasik (A. Drucker, R....
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...
Sudah lebih dari setahun sejak pencabutan dan koreksi Januari 2017. Apakah ada berita? Jika tidak apakah ini normal untuk validasi selama ini? Saya berharap itu akan mendapat banyak perhatian. Adakah yang diketahui berbicara untuk mendukung / meragukan hasil kuasi
Saya membaca " Apakah P Versus NP Secara Independen? " Tetapi saya bingung. Dipercaya secara luas dalam teori kompleksitas bahwa . Pertanyaan saya adalah bagaimana jika ini tidak dapat dibuktikan (katakanlah di ). (Mari kita asumsikan bahwa kita hanya mengetahui bahwa independen dari tetapi tidak...
The lemma memompa untuk bahasa reguler dapat dibuktikan dengan mempertimbangkan negara yang terbatas robot yang mengakui bahasa dipelajari, memetik string dengan lebih panjang daripada jumlah kantor negara, dan menerapkan prinsip mengesampingkan. Namun, memompa lemma untuk bahasa bebas konteks...
Apakah mungkin untuk menguji secara algoritmik apakah bilangan yang dihitung rasional atau bilangan bulat? Dengan kata lain, apakah mungkin bagi perpustakaan yang mengimplementasikan angka yang dapat dihitung untuk menyediakan fungsi isIntegeratau isRational? Saya menduga itu tidak mungkin, dan...
Baru-baru ini, Watrous et al membuktikan bahwa QIP (3) = PSPACE hasil yang luar biasa. Ini adalah hasil yang mengejutkan bagi diri saya untuk sedikitnya dan itu membuat saya berpikir ... Saya bertanya-tanya bagaimana jika Komputer Quantum dapat disimulasikan secara efisien oleh Komputer Klasik....
IP = PSPACE terdaftar sebagai contoh kanonik dari hasil non-relativizing, dan bukti untuk ini adalah bahwa ada oracle sedemikian sehingga , sementara {\ sf CoNp} ^ O \ subseteq {\ sf PSPACE} ^ O untuk semua nubuat O .OOOcoNPO⊈IPOcoNPO⊈IPO{\sf coNP}^O \not\subseteq {\sf
Saya berpikir bahwa teorema hierarki ukuran untuk kompleksitas sirkuit dapat menjadi terobosan besar di bidang ini. Apakah ini pendekatan yang menarik untuk pemisahan kelas? Motivasi untuk pertanyaan itu adalah yang harus kita katakan ada beberapa fungsi yang tidak dapat dihitung dengan ukuran...
Telah diketahui bahwa kumpulan bahasa yang memiliki sistem bukti interaktif dua-verver, di mana verifier berjalan dalam polinomial-time (MIP), adalah NEXP. Tetapi adakah batas yang diketahui tentang kekuatan bukti interaktif seperti itu ketika kaum proversi dibatasi kekuasaannya? Misalnya, apa...
Sebuah penutup tepi adalah bagian dari tepi grafik sehingga setiap titik dari grafik berdekatan dengan setidaknya satu tepi penutup. Dua makalah berikut mengatakan bahwa menghitung penutup tepi adalah #P -lengkap : FPTAS Sederhana untuk Menghitung Penutup Tepi dan Menghasilkan Tepi Tepi dari Grafik...