Dapatkah saya mengikat kardinalitas suatu set jika pengujian untuk keanggotaan di dalamnya diketahui sebagai NP-complete?

Saya ingin memiliki ikatan pada kardinalitas dari set grafik disk unit dengan simpulDiketahui bahwa memeriksa apakah suatu grafik adalah anggota dari set ini adalah NP-hard. Apakah ini mengarah pada batas yang lebih rendah pada kardinalitas, dengan asumsi P NP? $N$ $\neq$

Misalnya, anggap ada pengurutan pada semua grafik dengan simpulAkankah NP-hardness menyiratkan kardinalitas melebihi , dalam hal itu Anda dapat menguji keanggotaan dalam waktu polinomial dengan melakukan pencarian biner melalui set? Saya pikir ini akan menganggap bahwa Anda telah entah bagaimana menyimpan set dalam memori ... Apakah ini diizinkan? $N$ $2^N$

Definisi: Grafik adalah grafik unit disk jika setiap titik dapat dikaitkan dengan unit disk di pesawat, sehingga simpul terhubung setiap kali disk mereka berpotongan.

Berikut ini adalah referensi tentang kekerasan NP pengujian keanggotaan untuk grafik disk unit: http://disco.ethz.ch/members/pascal/refs/pos_1998_breu.pdf

cc.complexity-theory graph-theory David Choi
sumber

Saya bertanya-tanya, apakah ada contoh di mana teknik ini memberikan batas bawah paling dikenal pada ukuran beberapa set? Itu akan menjadi aplikasi kombinatorial keren tidak langsung dari teori kompleksitas.

Sasho Nikolov

Terima kasih atas bantuannya. Kedua jawaban itu bermanfaat dan berwawasan luas; Saya akan menerima salah satu tanpa yang lain.

David Choi

Jawaban:

Saya tidak yakin apakah Anda menanyakan pertanyaan ini untuk teknik atau jawabannya, tetapi ada makalah baru-baru ini oleh McDiarmid dan Mueller di mana mereka menunjukkan jumlah grafik unit-disk (berlabel) pada simpul adalah ; lihat http://homepages.cwi.nl/~mueller/Papers/countingDGs.pdf . $n$ $2^{(2 + o(1))n}$

Bart Jansen
sumber

Teorema Mahaney menyatakan bahwa set NP-lengkap jarang ada jika P = NP. Oleh karena itu, dengan asumsi menyiratkan batas bawah super-polinomial pada jumlah instance dalam set -lengkap, untuk banyak . Artinya, jika , maka setiap set -Lengkap harus memiliki beberapa sehingga untuk jauh-banyaknya bilangan bulat , set berisi setidaknya string dengan panjang . $P \neq NP$ $n$ $NP$ $n$ $P \neq NP$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

H. Buhrman dan JM Hitchcock membuktikan batas bawah ( ) ketat, kecuali hierarki polinomial runtuh. $2^{n^{\epsilon}}$

[1] H. Buhrman dan JM Hitchcock, NP-Hard Set Secara Eksponensial Padat Kecuali jika TNN ⊆ NP / poli, Dalam Konferensi IEEE tentang Kompleksitas Komputasi, halaman 1-7, 2008

[2] Eric Allender, Laporan Status pada Pertanyaan P vs. NP, Kemajuan dalam Komputer, Volume 77, 2009, Halaman 117-147

Mohammad Al-Turkistany
sumber

[Mah82] SR Mahaney. Set lengkap lengkap untuk NP: Solusi dugaan oleh Berman dan Hartmanis , Jurnal Ilmu Komputer dan Sistem 25: 130-143, 1982.

Marzio De Biasi

Setiap set NP-complete memiliki kardinalitas yang tak terbatas. Anda mungkin bermaksud bahwa P ≠ NP menyiratkan batas bawah super-polinomial pada jumlah instance

, untuk banyak

. Perhatikan juga bahwa

super-polinomial tanpa bentuk yang Anda berikan.

n

$n$

n

$n$

2^{(\log n)^{2}}

$2^{(\log n)^2}$

András Salamon

Terima kasih András, komentar Anda dimasukkan dalam jawabannya.

Mohammad Al-Turkistany

@Mohammad: buat batas bawah

, atau

: itulah yang berarti superpolinomial.

2^{ω (\log n)}

$2^{\omega(\log n)}$

n^{ω (1)}

$n^{\omega(1)}$

Sasho Nikolov

@ Sasho, H. Buhrman dan JM Hitchcock membuktikan batas bawah (

) yang saya sebutkan dalam jawaban saya, kecuali hierarki polinomial runtuh. H. Buhrman dan JM Hitchcock, NP-Hard Sets Secara Eksponensial Padat Kecuali jika TNN ⊆ NP / poli, Dalam Konferensi IEEE tentang Kompleksitas Komputasi, halaman 1-7, 2008

2^{n^{ϵ}}

$2^{n^{\epsilon}}$

Mohammad Al-Turkistany