Pertanyaan mengenai mesin oracle dalam teori kompleksitas komputasi. Oracles dapat berfungsi sebagai indikator bahwa pemisahan antara kelas kompleksitas berada di luar ruang lingkup teknik pembuktian tertentu.
Tetapkan i oioio - S U B E X PSUBEXPSUBEXP untuk menjadi kelas bahasa LLL sedemikian rupa sehingga ada bahasa dan untuk tak terhingga banyaknya , dan menyetujui semua contoh panjang . (Yaitu, ini adalah kelas bahasa yang dapat "dipecahkan secara tak terhingga, dalam waktu subeksponensial".)L ′ ∈ ∩...
Dalam banyak domain, ada teknik kanonik yang harus dikuasai semua orang di bidang ini. Misalnya, untuk pengurangan logspace, "trik bit" untuk komposisi yang terdiri dari tidak membangun output penuh dari fungsi yang dikomposisikan, tetapi selalu meminta untuk menghitung ulang hasil untuk setiap bit...
Secara umum, query-tape untuk oracle diperhitungkan dalam kompleksitas ruang TM. Namun, tampaknya masuk akal untuk memungkinkan rekaman-saja oracle-tape (seperti yang digunakan dalam pengurangan ruang-L). Apakah konstruksi seperti itu bermanfaat? Apakah itu menghasilkan hasil yang sangat tidak...
Nah, judulnya cukup banyak mengatakan itu semua. Pertanyaan menarik di atas ditanyakan oleh komentator Jay di blog saya (lihat di sini dan di sini ). Saya menduga keduanya bahwa jawabannya adalah ya dan bahwa ada bukti yang relatif sederhana, tetapi saya tidak dapat melihatnya begitu saja. (Namun,...
Misalkan adalah pohon derajat konstan yang strukturnya tidak kita ketahui. Masalahnya adalah untuk mengeluarkan pohon dengan menanyakan pertanyaan dari formulir: "Apakah simpul terletak pada jalur dari simpul ke simpul ?". Asumsikan bahwa setiap permintaan dapat dijawab dalam waktu yang konstan...
Saya baru saja membaca pertanyaan " Apakah faktorisasi bilangan bulat merupakan masalah NP-complete? " ... jadi saya memutuskan untuk menghabiskan sebagian dari reputasi saya :-) mengajukan pertanyaan lain memiliki :QQQP(Q is trivial)≈1P(Q is trivial)≈1P(\text{Q is trivial}) \approx 1 Jika adalah...
Latar Belakang Hal ini diketahui bahwa ada sebuah ramalan AAA seperti itu, PSPACEA≠PHAPSPACEA≠PHAPSPACE^A \neq PH^A . Bahkan diketahui bahwa pemisahan relatif terhadap oracle acak. Secara informal, seseorang mungkin menafsirkan ini berarti bahwa ada banyak nubuat yang PSPACEPSPACEPSPACE dan...
Dalam "Quantum Computation and Quantum Information" Mike dan Ike, algoritma Grover dijelaskan dengan sangat terperinci. Namun, dalam buku ini, dan dalam semua penjelasan yang saya temukan online untuk algoritma Grover, tampaknya tidak disebutkan tentang bagaimana Oracle dibangun, kecuali kita sudah...
Cara paling umum di mana nubuat muncul dalam teori kompleksitas adalah sebagai berikut: Sebuah nubuat tetap tersedia untuk, katakanlah, mesin Turing dengan sumber daya terbatas tertentu, dan seseorang mempelajari bagaimana oracle meningkatkan daya komputasi mesin. Namun, ada cara lain di mana...
Dalam makalah berjudul "On Deniability dalam Common Reference String dan Random Oracle Model," tulis Rafael Pass: Kami mencatat bahwa ketika membuktikan keamanan sesuai dengan definisi nol-pengetahuan standar dalam model RO [Random Oracle], simulator memiliki dua keunggulan dibandingkan...
Sederhananya: apa korespondensi antara mesin Turing dengan oracle, dan keluarga sirkuit seragam dengan oracle? Bagaimana yang terakhir didefinisikan untuk mendapatkan model komputasi yang sama, untuk mesin Turing oracle yang diberikan? Ini mungkin pertanyaan mendasar, tetapi tidak jelas ke mana...
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...
Apakah NPNP∩coNP=NPNPNP∩coNP=NP\mathsf{NP^{NP \,\cap\, coNP}=NP}hold? Jelas NPNP≠NPNPNP≠NP\mathsf{NP^{NP}\neq NP} , tetapi bagi saya sepertinya NP∩coNPNP∩coNP\mathsf{NP\cap coNP} adalah "deterministik" yang membuat saya percaya ini benar. Apakah ada bukti sederhana (atau mungkin hanya berdasarkan...
Masalah penghentian diketahui tidak dapat diperhitungkan. Namun, dimungkinkan untuk secara "kompres" informasi secara eksponensial tentang masalah penghentian, sehingga pengompresannya dapat dihitung. Lebih tepatnya, adalah mungkin untuk menghitung dari deskripsi mesin Turing dan saran bit...
Pertanyaan ini mungkin memiliki jawaban yang jelas ... tetapi inilah pertanyaannya. Secara intuitif, ini adalah pernyataan masuk akal berikut - "mesin dengan subrutin A yang pada gilirannya memiliki subrutin B sama dengan mesin dengan subrutin A yang memiliki akses ke subrutin B". Untuk...
Dalam sebuah makalah tentang merelatifkan perhitungan logspace, Ladner dan Lynch membangun sebuah oracle relatif terhadap yang . Ada beberapa contoh yang lebih patologis dalam hal ini dalam literatur. Saya telah membaca beberapa makalah tentang kelas ruang kecil yang direlatifikasi, dan salah satu...
Saya ingin tahu apakah ada dunia yang direlatifikasi di mana . Saya juga tertarik untuk mengetahui apakah ada dunia yang direlatifikasi di mana .PA=NPA≠PPAPA=NPA≠PPA{\bf P^A}={\bf NP^A}\not = {\bf PP^A}PB≠NPB=PPBPB≠NPB=PPB{\bf P^B} \not = {\bf NP^B} = {\bf
Biarkan menjadi masalah lengkap EXP. Kemudian, .P A = N P AAAAPA=NPAPA=NPAP^A = NP^A Mari ada beberapa oracle yang memperhitungkan rekening permintaan yang (TM di P) akan membuat, dan kita bisa mendapatkan .M P B ≠ N P BBBBMMMPB≠NPBPB≠NPBP^B \neq NP^B Pertanyaan: Apakah kami memiliki hasil oracle...
Saya belum dapat menemukan sebuah pernyataan yang berkaitan dan N P R P dalam literatur; pointer akan dihargai.MAMA\mathsf{MA}NPRPNPRP\mathsf{NP}^\mathsf{RP} Saya percaya mereka setara: : The N P Mesin menebak tali Merlin, dan R P oracle memverifikasi string sebagai Arthur
Generator kebal didefinisikan sebagai berikut: Biarkan menjadi hubungan NP, dan menjadi mesin yang menerima . Secara tidak resmi, sebuah program adalah generator yang kebal jika, pada input , ia menghasilkan pasangan instance-saksi , dengan , menurut distribusi di mana setiap musuh...