Versi terbatas masalah Clique?

Pertimbangkan versi masalah Clique berikut ini di mana input berukuran dan kami diminta untuk menemukan klik ukuran . Batasannya adalah prosedur pengambilan keputusan tidak dapat mengubah grafik input menjadi representasi lain dan tidak dapat menggunakan representasi lain untuk menghitung jawabannya, selain bit tambahan di luar grafik input. Bit tambahan dapat digunakan misalnya dalam algoritma brute-force untuk melacak status pencarian lengkap untuk klik, tetapi prosedur pengambilan keputusan dipersilakan untuk menggunakannya dengan cara lain yang masih memutuskan masalah. $n$ $k$ $\log(n^k)$

Adakah yang diketahui saat ini tentang kerumitan ini? Apakah ada pekerjaan yang dilakukan pada pembatasan lain dari Clique, dan jika demikian, dapatkah Anda mengarahkan saya ke pekerjaan seperti itu?

complexity-theory time-complexity ShyPerson
sumber

Apakah Anda ingin konstanta dalam sama dengan ukuran klik ?

k

$k$

\lg n^{k}

$\lg n^k$

k

$k$

Lucas Cook

@LucasCook Ya.

ShyPerson

Ini terdengar seperti Anda bertanya apakah masalah klik-lengkap NP dapat diselesaikan dalam ruang logaritmik. Menggunakan mesin Turing, satu kaset hanya bisa dibaca dan menyimpan grafik input. Pita lainnya dibatasi sehingga ada ruang yang tersedia untuk beberapa konstan . Kelas masalah yang dapat dipecahkan dalam model ini dikenal sebagai , ruang logaritmik deterministik. (Lihat wikipedia atau di kebun binatang kompleksitas ) $c \lg n$ $c$ $L$

Tidak diketahui apakah , tetapi jawaban positif akan menyiratkan bahwa , sehingga Anda (hampir pasti?) Tidak akan menemukan jawaban. dan menyiratkan , yang menyiratkan . $\mathrm{CLIQUE} \in L$ $P = NP$ $L \subseteq P \subseteq NP$ $\mathrm{CLIQUE} \in L$ $\mathrm{CLIQUE} \in P$ $P = NP$

Edit jika saya salah mengartikan masalah:

Jika Anda bermaksud bahwa dalam sama dengan ukuran klik (yaitu jumlah skala memori dengan input ), maka ada algoritma brute force sederhana: Anda dapat mengulang semua set yang mungkin dari node dan periksa apakah mereka membentuk -clique. Titik awal untuk mencari solusi yang lebih baik mungkin menjadi referensi [1]. $k$ $\lg n^k = k \lg n$ $k$ $k$ $k$ $k$

[1] Virginia Vassilevska, "Algoritma yang efisien untuk masalah klik" tautan pdf

Lucas Cook
sumber

@ShyPerson Ok. String input sering tidak dapat diubah dalam model terbatas ruang (seperti ruang TM linear di

atau ), sehingga mungkin tempat yang baik untuk dilihat. Saya tidak yakin dengan cara formal untuk mengatakan bahwa "Anda tidak dapat membuat representasi lain" selain hanya membatasi ruang. Jika saya diberi ruang untuk membuat salinan , apa sebenarnya yang dimaksud dengan representasi lain? Bagaimana jika saya "secara tidak sengaja" membangun representasi yang cukup untuk grafik yang jarang atau dapat dikompres?

L

$L$

N L

$NL$

G

$G$

Lucas Cook

k C L I Q U E

$\mathrm{kCLIQUE}$ tidak lengkap NP! (kecuali )

P = N P

$\mathrm{P}= \mathrm{NP}$

Alex ten Brink

@AlextenBrink Apakah maksud Anda bahwa kCLIQUE adalah masalah fungsi? Saya mengubah nama menjadi CLIQUE di atas (saya selalu membingungkan mereka!), Tapi aneh bagi saya untuk mengatakan kCLIQUE ada di NP jika Anda maksudkan masalah fungsinya.

Lucas Cook

Dimaksudkan searchmasalah, dalam hal ini.

Lucas Cook

k C L I Q U E

$\mathrm{kCLIQUE}$ adalah masalah

untuk

diperbaiki , sedangkan

memiliki

sebagai bagian dari input. Dengan memeriksa semua subgraf berukuran

Anda memiliki algoritma

, yang polinomial jika

diperbaiki tetapi superpolinomal jika misalnya

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

C L I Q U E

$\mathrm{CLIQUE}$

k

$k$

k

$k$

O (n^{k})

$O(n^k)$

k

$k$

k = Θ (n)

$k=\Theta(n)$

Alex ten Brink

Versi terbatas masalah Clique?

Jawaban: