Mengingat grafik diarahkan dan dua simpul . Sepasang jalur sederhana dari ke adalah edge disjoint jika mereka tidak berbagi edge.G=(V,E)G=(V,E)G = (V,E)s,t∈Vs,t∈Vs,t \in Vp1,p2p1,p2p_1,p_2sssttt Menggunakan aliran maks, mudah untuk memutuskan apakah ada sepasang jalur disjoint ujung dari ke ....
Rumus CNF monoton dengan istilah m pada n variabel ( ) adalah rumus dari bentuk f ( x 1 , ... , x n ) = ⋀ C i , di mana setiap C i adalah ATAU dari beberapa bagian dari variabel x 1 , … , x n , dan i berkisar dari 1 hingga m .x1,…,xnx1,…,xnx_1,\ldots,x_nf(x1,…,xn)=⋀Cif(x1,…,xn)=⋀Cif(x_1,\ldots,x_n)...
Saya membaca makalah survei Watrous yang sangat bagus di atas kertas tentang teori kompleksitas kuantum. Di dalamnya ia menyatakan bahwa akan mengejutkan jika masalah lengkap QMA ditemukan memiliki janji yang kosong (Ie Be a language). Kenapa begitu? Apakah itu ada hubungannya dengan fakta bahwa...
Diberikan grafik campuran G=(V,E,A)G=(V,E,A)G=(V,E,A) dengan tepi EEE dan busur AAA , cari kecocokan dalam EEE yang meminimalkan jumlah busur dalam G/MG/MG/M , di mana G/MG/MG/M diperoleh dari GGG dengan mengontrak simpul yang cocok dan menghapus busur paralel. Apakah (versi keputusan) masalah ini...
Misalkan adalah bahasa Boolean, dengan string hingga . Biarkan menjadi jumlah string dalam dengan panjang . Untuk fungsi dari bilangan bulat positif ke bilangan real positif, memiliki kepadatan atas jika untuk semua cukup besar .L.LL{ 0 , 1 }{0,1}\{0,1\}L.nLnL_nL.LLnnnd( n )d(n)d(n)L.LL d( n...
Bahasa L.LL ada di kelas D PDPDP jika ada dua bahasa L 1 ∈ NPL1∈NPL1 \in NP dan L 2 ∈ c o NPL2∈coNPL2 \in coNP sehingga L=L1∩L2L=L1∩L2L = L1 \cap L2 Sebuah kanonik DPDPDP masalah -Lengkap adalah SAT-UNSAT: diberikan dua ekspresi 3-CNF, FFF dan GGG , apakah benar bahwa FFF adalah satisfiable dan...
Konteks: Kami hanya mempertimbangkan digraf. Biarkan CYCLE menjadi bahasa grafik dengan siklus; itu adalah masalah NL-lengkap. Biarkan HASEDGE menjadi bahasa grafik dengan setidaknya satu sisi. Kemudian sepele, tidak lagi NL-hard, sementara tetap seperti itu.CYCLE∪HASEDGECYCLE∪HASEDGE\text{CYCLE}...
Dalam buku Arora-Barak, dalam definisi fungsi yang dapat dikonstruksikan waktu, dikatakan bahwa menggunakan fungsi yang tidak dapat dikonstruksikan oleh waktu dapat mengarah pada "hasil yang tidak normal". Apakah ada yang punya contoh "hasil yang tidak biasa" seperti itu? Saya telah mendengar...
Saya mencari contoh masalah sulit (dalam NP atau lebih keras) dari ilmu komputer yang dapat direduksi menjadi model proses fisik. Misalnya, maks-2-sat dapat dikurangi menjadi minimalisasi energi dalam model Ising. Saya ingin menemukan lebih banyak contoh pengurangan jenis
Apakah sulit untuk memperkirakan angka kromatik fraksional pada grafik derajat
Matriks Moore mirip dengan matriks Vandermonde tetapi memiliki definisi yang sedikit dimodifikasi. http://en.wikipedia.org/wiki/Moore_matrix Apa kompleksitas komputasi determinan dari yang diberikan n×nn×nn \times n rank penuh Moore matriks modulo suatu bilangan bulat? Can Moore penentu dikurangi...
Misalkan menjadi grafik yang tidak terarah. Sebuah dekomposisi V menjadi beberapa bagian yang menguraikan V i disebut dekomposisi Hamilton dari G jika subgraph disebabkan oleh masing-masing set V i adalah salah grafik Hamilton atau terdiri dari tepi tunggal dengan | V i | = 2 .G = ( V,...
Apakah menyiratkan E = N E ?E X P = N E X PEXP=NEXP\mathsf{EXP}=\mathsf{NEXP}E = N
Perhitungan dari mesin Turing nondeterministic (NTM) dikenal sebagai pohon konfigurasi, yang berakar pada konfigurasi awal. Setiap transisi dalam program diwakili oleh tautan ayah-anak di pohon ini. Pohon serupa juga dapat dibangun untuk memvisualisasikan perhitungan mesin probabilistik dan...
Wikipedia menulis: FPT berisi masalah traktable parameter tetap, yang dapat diselesaikan dalam waktu untuk beberapa fungsi yang dapat dihitung f . Biasanya, fungsi ini dianggap sebagai eksponensial tunggal, seperti 2 O ( k ) tetapi definisi tersebut mengakui fungsi yang tumbuh lebih cepat. Ini...
Deciding Graph Homomorphism secara umum NP-Complete. Apakah ada hasil yang mempelajari masalah ini ketika grafik yang mendasari memiliki struktur aljabar (seperti memutuskan homomorfisme dari grafik Cayley atau Cayley coset ke grafik lain dengan beberapa struktur tertentu juga)? Selain hasil...
Untuk merayakan ulang tahun Alan Turing, Google menerbitkan doodle yang menunjukkan mesin. Mesin seperti apa doodle itu? Bisakah itu mengekspresikan bahasa Lengkap Turing? Ada perbedaan yang jelas dengan mesin turing klasik: pita terbatas, kendala dalam bagaimana negara dapat dihubungkan,...
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
Dalam kebanyakan sistem bukti probabilistik (teorema PCP, misalnya), probabilitas kesalahan biasanya didefinisikan pada sisi false-positive, yaitu definisi tipikal dapat terlihat seperti: jika maka verifier selalu menerima, tetapi dalam kasus lain kemungkinan penolakan setidaknya 1/2.x ∈ Lx∈Lx \in...