Apakah ada bahasa NP-complete yang mengandung tepat setengah dari instance n-bit?

25

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.L{0,1}n1

|L{0,1}n|=2n1
Ln
Andras Farago
sumber
4
Akan sangat mengejutkan jika tidak ada tetapi memikirkannya selama beberapa menit tidak dapat menemukan konstruksi.
Kaveh
2
FWIW ada yang NP-hard dan NP / POLY ...L
Neal Young
Untuk pengkodean biner bijective dari rumus CNF, { e ( φ ) 1 | φ memuaskan } { e ( φ ) 0 | φ tidak memuaskan } harus bekerja. e{e(φ)1 | φ}{e(φ)0 | φ}
Klaus Draeger
4
@KlausDraeger Ketidakpuasan bukanlah properti NP, kecuali NP = co-NP.
Andras Farago
Apakah ada oracle sehingga tidak ada LN P - C o m p l e t e O dengan properti ini? OLNPCompleteO
Erfan Khaniki

Jawaban:

24

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 

  • untuk semua formula dan untuk semua tugas kebenaran τ { 0 , 1 } | φ | , | Φ | = | Φ , τ | .φτ{0,1}|φ||φ|=|φ,τ|
  • dapat dihitung secara polinomial waktu.|φ||φ|
  • jumlah rumus dengan panjang yang dikodekan adalah waktu-polinomial yang dapat dihitung.n

Pertimbangkan

L:={φφSAT}{φ,ττφ and σ<τ σφ}

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

τφ and σ<τ σφ
1φφ

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+2LnLφn2|φ|

Ryan O'Donnell
sumber
10
Bahkan jika ini adalah solusi yang diinginkan, ini adalah jawaban yang jelas untuk tautan saja.
user2943160
untuk menjadi jelas, tidak ada yang istimewa tentang SAT, ini akan bekerja dengan predikat verifikasi untuk masalah NP-lengkap.
Kaveh
ϕ¬ϕτ
@Neal, misalkan V (x, y) menjadi pemverifikasi untuk masalah NP-complete. Pertimbangkan W (x, b, y): = V (x, y) = b. Itu masih NP-complete dan masing-masing y adalah saksi baik untuk x, 0 atau x, 1. Tidak sebagus SAT sekalipun.
Kaveh
A={(ϕ,b,τ):(τ satisfies ϕ)b=1}?
B={(ϕ,b):τSATb=1}ABAC={(ϕ,b):τ. [(τ satisfies ϕ)b=1]}
8

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.]

LL=n:=|L{0,1}n|=2n1L{0,1}n{0,1}nLNPf:{0,1}{0,1}xLf(x)LfNP=coNPfNPcoNP

EXPcoNPNTIME(2(logn)O(1))=:NQPPHNQPPHNQP

L

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).

L

Joshua Grochow
sumber