Dalam bukunya Computational Complexity , Papadimitriou mendefinisikan FNP sebagai berikut: Misalkan adalah bahasa dalam NP . Dengan Proposisi 9.1, ada polinomial-waktu decidable, polynomially seimbang hubungan sehingga untuk semua string : Ada string dengan jika dan hanya jika . Masalah fungsi...
HT( n )HT(n)HT(n)nnnB B ( n ) = maks HT( n )BB(n)=maksHT(n)BB(n) = \max HT(n) Apa yang bisa kita katakan tentang angka terbesar kedua di ? Sebut ini .B B 2 ( n )HT( n )HT(n)HT(n)BB2(n)BB2(n)BB_2(n) B B ( n ) B B ( n ) - B B 2 ( n )BB2(n)BB2(n)BB_2(n) sepele tidak dapat dihitung, karena...
Kita tahu masalah menghitung jumlah penugasan yang memuaskan dalam formula boolean umum yang diberikan (CNF-SAT), formula DNF yang diberikan, atau bahkan formula 2SAT yang diberikan adalah masalah # P-complete . Sekarang, pertimbangkan CNF-SAT tanpa literal negatif (tidak , selalu A ). Masalah...
Dalam permainan kerikil pada garis ada N + 1 node berlabel 0 hingga N. Permainan dimulai dengan kerikil pada simpul 0. Jika ada kerikil pada simpul i, Anda dapat menambah atau menghapus kerikil dari simpul i +1. Tujuannya adalah untuk menempatkan kerikil pada simpul N, tanpa menempatkan banyak...
Katakanlah kita memiliki properti grafik yang dapat diperiksa dalam waktu polinomial nondeterministik, dan bukti dalam sistem formal yang lemah (katakanlah RCA 0 ) bahwa properti tersebut tertutup kecil. Bisakah kita mengatakan sesuatu tentang kekuatan sistem formal, yang mampu membuktikan bahwa...
Diberi sebagai terbatas (deterministik atau nondeterministik, saya pikir ini tidak terlalu penting) otomat A dan ambang n , apakah A menerima kata yang mengandung paling banyak n huruf berbeda? (Dengan k huruf yang berbeda maksudku aabaa memiliki dua huruf berbeda, a dan b .) Saya menunjukkan...
Saya punya (mudah-mudahan sederhana, mungkin bodoh) pertanyaan di kertas tengara Babai yang menunjukkan bahwa quasipolynomial.G IGsaya\mathsf{GI} Babai menunjukkan cara menghasilkan sertifikat yang dua grafik untuk isomorfik, dalam waktu kuasipolinomial
Katakanlah kita menginginkan bahasa pemrograman fungsional yang murni, seperti Haskell atau Idris, yang ditujukan untuk pemrograman sistem tanpa pengumpulan sampah dan tidak memiliki runtime (atau setidaknya tidak lebih dari "runtimes" C dan Rust). Sesuatu yang bisa berjalan, lebih atau kurang,...
Bukti Omer Reingold yang memberikan algoritma untuk USTCON (Dalam U ndirected grafik dengan simpul khusus dan , mereka ConL=SLL=SLL=SLtsssttt nected?) Hanya menggunakan logspace. Ide dasarnya adalah untuk membangun grafik expander dari grafik asli, dan kemudian berjalan di grafik expander. Grafik...
Ada trik lama untuk menuliskan algoritma yang, jika P = NP, memecahkan SAT dalam waktu polinomial. Pada dasarnya, satu daftar semua mesin waktu polinomial dan multi-tugas di atasnya. Apakah ada trik analog untuk fungsi satu arah (atau bahkan fungsi pintu jebakan satu arah)? Yaitu, dapatkah kita...
Dalam rangka belajar automata Angluin ini , sebuah tujuan siswa untuk belajar bahasa reguler L⊆Σ∗L⊆Σ∗L\subseteq \Sigma^* dengan meminta dua jenis pertanyaan untuk gurunya: Kueri kata: diberikan w∈Σ∗w∈Σ∗w\in \Sigma^* , adalahw∈Lw∈Lw\in L ? Kueri kesetaraan: diberi bahasa K⊆Σ∗K⊆Σ∗K\subseteq...
Setelah membaca pertanyaan terakhir "Apakah komplemen bebas konteks?" {www∣...}{www∣...}\{ www \mid ...\}; Saya ingat masalah yang sama yang tidak bisa saya tolak: Apakah konteks gratis?L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L={ww′∣w,w′∈{0,1}∗∧|w|=|w′|∧HamDist(w,w′)>1}L = \{ ww' \mid...
Pertimbangkan permainan berikut pada grafik tertimbang GGG diarahkan dengan chip di beberapa node. Semua node GGG ditandai dengan A atau B. Ada dua pemain, Alice dan Bob. Tujuan dari Alice (Bob) adalah untuk menggeser chip ke node yang ditandai oleh A (B). Awalnya Alice dan Bob memiliki...
Dalam Kasus Terburuk Secara Fungsional Murni , Daftar Urut Waktu Konstan Catenable , Brodal et al. hadir pohon seimbang murni fungsional dengan O (1) menyatukan dan O (lg n) menyisipkan, menghapus, dan menemukan. Struktur data agak rumit. Apakah ada pohon pencarian seimbang yang lebih sederhana...
Diketahui bahwa untuk pembelajaran PAC, ada kelas konsep alami (misalnya himpunan bagian dari daftar keputusan) yang terdapat kesenjangan polinomial antara kompleksitas sampel yang diperlukan untuk pembelajaran teori informasi oleh pelajar yang tidak terikat secara komputasi, dan kompleksitas...
Biarkan poin berbeda duduk di . Kita katakan poin dan adalah tetangga jika | ij | <3 \ pmod {n-2} , artinya setiap titik bertetangga dengan titik dengan indeks dalam 2 , membungkus.R 2 i j1...n1...n1 ... nR2R2\mathbb{R}^2iiijjj|i−j|<3(modn−2)|i−j|<3(modn−2)|i-j| < 3...
Apa masalah lain yang berbeda dari bahasa isomorfisme grafik dalam ? Bisakah Anda memberikan beberapa referensi?NP∩coAMNP∩coAMNP\cap coAM Update: Saya lupa menyebutkan bahwa saya tertarik dalam bahasa yang tidak dikenal berada di
Algoritma aliran memerlukan pengacakan untuk sebagian besar untuk melakukan apa saja nontrivial, dan karena kendala ruang kecil, perlu PRG yang menggunakan sedikit ruang. Saya tahu dua metode yang telah dikutip untuk digunakan dalam algoritma streaming sejauh ini: kkk -bijaksana PRG independen...
Konsep skema berbagi rahasia sering dikaitkan dengan Shamir (A. Shamir, Cara berbagi rahasia , Comm. ACM, 22 (1979), hlm. 612-613.) Dan Blakey (GR Blakey, Safeguarding kunci kriptografi , di Proc. NCC, vol. 48, 1979, hlm. 313-317.) Ide keseluruhan adalah bahwa beberapa S rahasia tersembunyi dari...
Masalah pewarnaan grafik sudah cukup sulit bagi kebanyakan orang . Meski begitu, saya harus sulit dan menanyakan masalah tentang pewarnaan hypergraph. Pertanyaan. Algoritme efisien apa yang ada untuk menemukan pewarnaan tepi yang kurang lebih optimal untuk hypergraphs k-uniform? Detail...