Masalah Singkat di

Studi tentang representasi ringkas dari grafik diprakarsai oleh Galperin dan Wigderson di kertas dari tahun 1983, di mana mereka membuktikan bahwa untuk banyak masalah sederhana seperti menemukan segitiga dalam grafik, versi ringkas yang sesuai pada -Lengkap. Papadimitriou dan Yanakkakis melanjutkan penelitian ini, dan membuktikan bahwa untuk masalah Π yaitu N P -complete / P -complete, versi Succinct yang sesuai, yaitu Succinct Π masing-masing, N E X P -complete dan E X P -complete . (Mereka juga menunjukkan bahwa jika $\mathsf{NP}$$\Pi$$\mathsf{NP}$$\mathsf{P}$$\Pi$$\mathsf{NEXP}$$\mathsf{EXP}$$\Pi$adalah -lengkap, maka Ringkas Π adalah P S P A C E -complete.$\mathsf{NL}$$\Pi$$\mathsf{PSPACE}$

Sekarang pertanyaan saya adalah, apakah ada masalah diketahui yang, versi singkat yang sesuai dalam P ? Saya akan tertarik mengetahui tentang hasil terkait lainnya (baik hasil positif dan ketidakmungkinan, jika ada) yang mungkin saya lewatkan di atas. (Saya tidak dapat menemukan sesuatu yang menarik oleh pencarian google, karena kata-kata pencarian seperti ringkas, representasi, masalah, grafik menyebabkan hampir semua hasil kompleksitas! :))$\Pi$$\mathsf{P}$

Berikut adalah masalah menarik yang versi ringkasnya memiliki properti menarik. Tentukan Sirkuit-Ukuran- menjadi masalah: diberi fungsi Boolean sebagai string 2 n- bit, apakah fungsi ini memiliki sirkuit ukuran paling banyak 2 n / 2 ? Catatan Masalah ini di N P .$2^{n/2}$$2^n$$2^{n/2}$$NP$

Salah satu cara untuk mendefinisikan Ringkas-Sirkuit-Ukuran- adalah: untuk konstanta k , diberi n -input, n k -ukuran sirkuit C , kita ingin tahu apakah tabel kebenarannya adalah turunan dari Sirkuit-Ukuran - 2 n / 2 . Tapi ini masalah sepele: semua input yang merupakan rangkaian aktual adalah instance-ya. Jadi masalah ini adalah di P .$2^{n/2}$$k$$n$$n^k$$C$$2^{n/2}$$P$

Cara yang lebih umum untuk mendefinisikan Ringkas-Sirkuit-Ukuran- adalah: kita diberi sirkuit sewenang-wenang C dan ingin tahu apakah tabel kebenarannya mengkodekan instance Sirkuit-Ukuran- 2 n / 2 . Tetapi jika n adalah jumlah input ke C , m adalah ukuran C , dan m ≤ 2 n / 2 , kita dapat secara otomatis menerima: input itu sendiri adalah saksi untuk bahasa. Kalau tidak, kita memiliki m ≥ 2 n / 2 . Dalam hal itu, panjang input $2^{n/2}$$C$$2^{n/2}$$n$$C$$m$$C$$m \leq 2^{n/2}$$m \geq 2^{n/2}$$m$sudah besar, jadi kita bisa mencoba semua kemungkinan tugas dalam m O ( 1 ) waktu, mendapatkan tabel kebenaran fungsi, dan sekarang kita kembali ke masalah N P asli lagi. Jadi ini adalah masalah di N P yang versi singkat juga di N P .$2^n$$m^{O(1)}$$NP$$NP$$NP$

Masalah ini diyakini bukan -hard; lihat koran oleh Kabanets dan Cai (http://www.cs.sfu.ca/~kabanets/Research/circuit.html)$NP$

Mengingat bahwa bahkan memutuskan apakah grafik yang diwakili oleh representasi ringkas yang diberikan mengandung setidaknya satu sisi atau tidak setara dengan Sirkuit SAT dan karenanya NP-lengkap, tergoda untuk mengklaim bahwa properti menarik dari representasi ringkas harus NP-keras di bawah definisi yang sesuai dari "menarik." Klaim ini akan menjadi analogi teoritik-kompleksitas untuk teorema Rice . Sayangnya, menemukan analogi kompleksitas-teoretis yang paling umum dari teorema Rice adalah masalah terbuka , meskipun ada hasil yang memberikan beberapa bentuk analog-teoretis kompleksitas-seperti itu.

Saya tidak bermaksud ini menjadi jawaban tetapi akan membutuhkan terlalu banyak komentar. Semoga bermanfaat.

Seperti yang ditunjukkan Tsuyoshi, menggoda untuk menduga bahwa semua properti "non-sepele" itu keras (misalnya NP-hard). Namun, untuk menunjukkan ini, Anda perlu mendefinisikan non-sepele. Dalam teorema Rice, properti nontrivial adalah semua properti kecuali properti yang mencakup semua bahasa yang dapat dihitung dan properti yang tidak mencakup bahasa yang dapat dihitung. Itu kurang jelas apa definisi yang tepat dari non-sepele adalah untuk masalah ringkas. Jelas sifat-sifat yang mengandung semua string atau tidak ada string dalam P. Tapi ada yang lain di P juga. Sebagai contoh, properti yang pertandingan string yang agak tengah adalah 0. Atau Π berisi semua string dari 2 n bit sehingga setiap 2 n /$\Pi$$\Pi$$2^n$$2^n/x$-th bit adalah 1, di mana . Jadi, bagaimana kita mendefinisikan "sepele" untuk mencakup jenis properti ini?$x = n^{O(1)}$

Satu ide adalah untuk melihat yang "simetris": jika string s ada di Π , maka permutasi bit s juga ada di Π . Properti seperti ini hanya bergantung pada jumlah 1 bit dalam sebuah string. Dalam jawaban untuk pertanyaan yang dikaitkan Tsuyoshi, Ryan Williams memberikan tautan ke makalah ini yang menunjukkan bahwa semua masalah seperti itu sulit.$\Pi$$s$$\Pi$$s$$\Pi$

Gagasan lain bagaimana mendefinisikan "properti non-sepele"? Kita dapat melihat sebagai keluarga fungsi boolean (fungsi indikator properti untuk setiap panjang string). Tampak bagi saya bahwa sifat non-trivial adalah properti yang keluarga terkait fungsi boolean memiliki kompleksitas non-sepele. Sebagai contoh, dapatkah kita menunjukkan bahwa properti yang fungsi keluarga boolean yang terkait memiliki kompleksitas pohon keputusan linear sulit?$\Pi$