Apakah Ukuran Keanggotaan Saksi untuk Setiap Bahasa NP Sudah Dikenal?

13

Pertanyaan itu muncul pada saya ketika saya mendapatkan jawaban Dana Moshkovitz untuk topik lain .

Biarkan L menjadi NP Bahasa, dan membiarkan RL menjadi masing- NP hubungan. Kita tahu bahwa ada beberapa polinomial p sehingga:

∀x∈L,,∃w∈0,1p(|x|)(x,w)∈RL

Pernyataan di atas hanya mensyaratkan keberadaan seperti itu , tetapi tidak memaksanya ditentukan secara eksplisit . Sebaliknya, untuk setiap bahasa NP yang saya tahu, p sudah dikenal:pp

  • Untuk SAT, ukuran saksi sama dengan jumlah atom yang muncul dalam rumus.
  • Untuk Hamiltonicity, ukuran saksi adalah , di mana V adalah himpunan simpul.O(|V|)V
  • Untuk Grafik 3-Warna, ukuran saksi adalah , di mana V adalah himpunan simpul.O(|V|)V

Apakah ada eksis sebuah NP bahasa (bahkan yang buatan), yang kami tahu di sana ada beberapa polinomial berlari ukuran saksi, namun kita tidak dapat secara eksplisit menentukan p ?pp

cc.complexity-theory np MS Dousti
sumber
Untuk bahasa tertentu dalam NP, ada banyak hubungan NP yang memunculkannya. Apakah Anda bertanya tentang bahasa mana p polinomial minimal tidak diketahui (yaitu, di mana kita dapat mencoba meminimalkan polinomial dengan melihat hubungan berbeda yang menghasilkan L yang sama ), atau tentang hubungan di mana p polinomial yang sesuai tidak diketahui (tetapi kami tahu satu ada)? LpLp
Joshua Grochow
@ Joshua: Saya mungkin salah paham komentar Anda, tetapi jika kita tahu minimal atas semua hubungan untuk beberapa masalah NP-lengkap dan jika itu bukan nol, bukankah itu berarti P ≠ N P ? pP≠NP
Cong Han
@Cong: Anda benar. Saya kira maksud saya p minimal yang kita tahu , katakanlah, modulo asumsi standar / keadaan terkini dari seni. Sebagai contoh, saya percaya makalah STOC 2010 Ryan Williams menunjukkan bahwa jika ada hubungan untuk SAT dengan ukuran saksi , maka N E X P ⊈ P / p o l y , jadi menunjukkan hal seperti itu di luar pemahaman saat ini. o(n)NEXP⊈P/poly
Joshua Grochow
@ Yosua: Benar, tentu saja! Terima kasih, terima kasih.
Cong Han
2
Jika ada hubungan untuk Sirkuit SAT dengan ukuran saksi , di mana k adalah jumlah input ke sirkuit dan n adalah ukuran sirkuit, maka ya, N E X P ⊈ P / p o l y . k−ω(log⁡n)knNEXP⊈P/poly
Ryan Williams

Jawaban:

12

Jika Anda tidak keberatan dengan bahasa buatan, kami dapat membuat masalah seperti itu dengan menggunakan hampir semua angka k yang nilainya tidak diketahui oleh ahli matematika. Misalnya, kita tidak tahu nilai R (5,5) (angka Ramsey kelima ), atau ukuran minor yang tidak termasuk dalam keluarga dari grafik tanpa simpul (angka ini terbatas karena teorema Robertson-Seymour ), atau nilai BB (10), di mana BB () adalah singkatan dari fungsi Busy Beaver . Biarkan k sama dengan angka-angka ini. Kita tahu bahwa k adalah terbatas, tetapi kita tidak tahu nilai dari k.

Sekarang membangun beberapa masalah dalam NP mana saksi adalah ukuran . Dari atas kepala saya, saya tidak bisa memikirkan cara yang baik untuk melakukan ini, tapi di sini ada satu cara. Biarkan input menjadi deskripsi singkat dari grafik. Karena ukuran deskripsi adalah n, grafik berada pada banyak titik secara eksponensial. (Sebagai contoh, mungkin input adalah sirkuit yang menerima dua input x dan y dan memberitahu Anda jika (x, y) adalah kelebihan dalam grafik.) Pertanyaannya adalah untuk menentukan apakah grafik berisi jalan panjang n k . Masalah ini ada di NP karena prover dapat mengirim daftar simpul pada jalur secara berurutan, yang dapat diperiksa oleh verifier. Ukuran saksi adalah n k .O(nk)nknk

Robin Kothari
sumber