Apakah ada bahasa NP-complete (lebih disukai natural) , sehingga untuk setiap n ≥ 1 | L ∩ { 0 , 1 } n | = 2 n - 1 tahan? Dengan kata lain, L mengandung tepat setengah dari semua instance n- bit.
cc.complexity-theory
np
np-complete
Andras Farago
sumber
sumber
Jawaban:
Saya mengajukan pertanyaan ini beberapa tahun yang lalu dan Boaz Barak menjawabnya dengan positif .
Pernyataan ini setara dengan keberadaan bahasa -NP lengkap di mana | L n | dapat dihitung secara polinomial waktu.L |Ln|
Pertimbangkan formula Boolean dan SAT. Dengan menggunakan padding dan sedikit memodifikasi encoding formula kita dapat memastikan bahwa dan ¬ φ memiliki panjang yang sama.φ ¬φ
Mari menjadi encoding yang⟨ ⟩
Pertimbangkan
Sangat mudah untuk melihat bahwa adalah NP-lengkap.L
Jika , jumlah penugasan kebenaran yang memuaskan τ ⊨ φ dan ∃ σ < τ σ ⊨ φ sama dengan jumlah penugasan kebenaran yang memuaskan - 1 . Menambahkan φ itu sendiri berarti jumlah tugas kebenaran yang memuaskan untuk φ .φ∈SAT
Ada penugasan kebenaran. Setiap τ dapat memenuhi satisf atau ¬ φ (dan tidak keduanya). Untuk setiap formula φ , mempertimbangkan 2 ( 2 | φ | + 1 ) string ⟨ φ ⟩ , ⟨ ¬ φ ⟩ , ⟨ φ , τ ⟩ , dan ⟨ ¬ φ , τ ⟩ untuk τ ∈ { 0 ,2|φ| τ φ ¬φ φ 2(2|φ|+1) ⟨φ⟩ ⟨¬φ⟩ ⟨φ,τ⟩ ⟨¬φ,τ⟩ . Tepat 2 | φ | dari 2 ini | φ | + 1 + 2 string di L . Ini berarti bahwa jumlah string panjang n dalam L adalah jumlah rumus φ dari panjang yang disandikan n dikalikan dengan 2 | φ | yang dihitung polinomial-waktu.τ∈{0,1}|φ| 2|φ| 2|φ|+1+2 L n L φ n 2|φ|
sumber
Inilah saran mengapa mungkin sulit untuk memberikan contoh seperti itu, meskipun saya setuju dengan komentar Kaveh bahwa akan mengejutkan jika itu tidak ada. [Bukan jawaban, tapi terlalu lama untuk komentar.]
Tentu saja, ini juga merupakan jenis hal di mana seseorang akan datang dengan sebuah contoh dan kita akan dengan mudah melihat bagaimana hal itu mengatasi keberatan ini, tetapi saya hanya ingin membuang ini di luar sana untuk mengatakan bagaimana segala sesuatu dengan penambangan yang cukup sederhana dapat dilakukan. tidak akan berhasil (kecuali jika kepercayaan yang diyakini banyak orang salah).
sumber