Beberapa masalah optimisasi yang dikenal sebagai NP-hard pada grafik umum sepele dipecahkan dalam waktu polinomial (beberapa bahkan dalam waktu linier) ketika grafik input adalah pohon. Contohnya termasuk penutup simpul minimum, set independen maksimum, isomorfisme subgraph. Sebutkan beberapa...
Saat menyandikan logika menjadi asisten bukti seperti Coq atau Isabelle, pilihan perlu dibuat antara menggunakan dangkal dan penyisipan dalam . Dalam formula logis embedding dangkal ditulis langsung dalam logika prover teorema, sedangkan dalam formula logis embedding mendalam direpresentasikan...
Apa batas bawah terbaik saat ini untuk waktu dan kedalaman rangkaian untuk
Saya tertarik untuk mendapatkan pemahaman yang benar-benar solid tentang pengetikan yang tergantung. Saya telah membaca sebagian besar TaPL dan membaca (jika tidak sepenuhnya diserap) 'Jenis Ketergantungan' di ATTaPL . Saya juga membaca dan membaca sekilas banyak artikel tentang pengetikan yang...
Saya sedang mengedit naskah siswa. Mahasiswa itu berkomentar bahwa akan menyenangkan melihat contoh-contoh tulisan berkualitas dalam karya yang diterbitkan, dan saya menyadari bahwa saya tidak dapat benar-benar menghasilkan contoh-contoh bagus dari atas kepala saya. Apa contoh terbaik dari...
Mari saya mulai dengan beberapa contoh. Mengapa begitu sepele untuk menunjukkan CVP dalam P tetapi begitu sulit untuk menunjukkan LP dalam P; sementara keduanya adalah masalah P-complete. Atau anggap primality. Lebih mudah untuk menunjukkan komposit dalam NP daripada bilangan prima dalam NP (yang...
Kita tahu bahwa L⊆NL⊆PL⊆NL⊆P\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P} dan L⊆NL⊆L2⊆L⊆NL⊆L2⊆\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq polyLpolyL\mathsf{polyL} , di mana L2=DSPACE(log2n)L2=DSPACE(log2n)\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n) . Kita juga tahu bahwa...
Buku Arora dan Barak menyajikan anjak piutang sebagai masalah berikut: FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}FACTORING={⟨L,U,N⟩|(∃ a prime p∈{L,…,U})[p|N]}\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\} Mereka menambahkan,...
Teorema Ladner menyatakan bahwa jika P ≠ NP, maka ada hierarki tak terbatas dari kelas kompleksitas yang secara ketat berisi P dan secara ketat terkandung dalam NP. Buktinya menggunakan kelengkapan SAT di bawah banyak-satu pengurangan NP. Hirarki berisi kelas kompleksitas yang dibangun oleh semacam...
Misalkan saya memiliki grafik asiklik terarah dengan bobot bilangan real pada simpulnya. Saya ingin menemukan pemesanan topologi DAG di mana, untuk setiap awalan pemesanan topologis, jumlah bobot adalah non-negatif. Atau jika Anda lebih suka terminologi teoretis pesanan, saya memiliki urutan...
Hirarki Chomsky (–Schützenberger) digunakan dalam buku teks ilmu komputer teoretis, tetapi itu jelas hanya mencakup sebagian kecil dari bahasa formal (REG, CFL, CSL, RE) dibandingkan dengan Diagram Kompleksitas Kebun Binatang . Apakah hierarki memainkan peran dalam penelitian saat ini lagi? Saya...
Pada utas lain , Andrej Bauer mendefinisikan semantik denotasional sebagai: arti suatu program adalah fungsi dari makna bagian-bagiannya. Yang menggangguku tentang definisi ini adalah bahwa ia tampaknya tidak memilih apa yang biasanya dianggap sebagai semantik denotasional dari apa yang...
Ini pemahaman saya bahwa model Turing telah menjadi "standar" ketika menjelaskan perhitungan. Saya tertarik untuk mengetahui mengapa hal ini terjadi - yaitu, mengapa model TM menjadi lebih banyak digunakan daripada model lain yang setara secara teori (sepengetahuan saya), misalnya urs-Rekursi...
Saya mencari dugaan tentang algoritme dan kompleksitas yang dipandang kredibel oleh banyak orang di beberapa titik waktu, tetapi kemudian mereka ditolak, atau setidaknya tidak dipercaya, karena pemasangan kontra-bukti. Berikut adalah dua contoh: Hipotesis oracle acak: hubungan antara kelas-kelas...
Pertanyaan: Bagaimana cara 'taktik' bekerja di asisten bukti? Mereka tampaknya menjadi cara menentukan bagaimana menulis ulang istilah menjadi istilah yang setara (untuk beberapa definisi 'setara'). Agaknya ada aturan formal untuk ini, bagaimana saya bisa belajar apa itu dan bagaimana mereka...
Hari ini Ryan Williams memposting artikel di arXiv (sebelumnya muncul di SIGACT News) berisi versi yang kurang teknis dari teknik batas bawah ACC baru-baru ini. Pertanyaan saya bukan tentang teknik itu sendiri (tentu saja layak pujian yang sangat besar), tetapi tentang gaya kertas. Dalam abstrak,...
Diketahui bahwa metrik TSP dapat diperkirakan dalam dan tidak dapat diperkirakan lebih baik dari 1231.51.51.5 dalam waktu polinomial. Apakah sesuatu yang diketahui tentang menemukan solusi pendekatan dalam waktu eksponensial (misalnya, kurang dari2nlangkah dengan hanya ruang polinomial)? Misalnya...
Secara informal, kompleksitas Kolmogorov dari string adalah panjang dari program terpendek yang menghasilkan x . Kita dapat mendefinisikan gagasan 'string acak' yang menggunakannya ( x adalah acak jika K ( x ) ≥ 0,99 | x | ) Mudah untuk melihat bahwa sebagian besar string adalah acak (tidak ada...
Saya selalu mengalami kesulitan dalam memahami pentingnya Integrality Gap (IG) dan terikat padanya. IG adalah rasio (kualitas) jawaban integer optimal untuk (kualitas) solusi nyata optimal dari relaksasi masalah. Mari kita pertimbangkan vertex cover (VC) sebagai contoh. VC dapat dinyatakan sebagai...
Jika Anda dapat mengubah nama pemrograman dinamis, apa