Masalah di luar P yang tidak P-keras

Saat membaca jawaban oleh Peter Shor dan pertanyaan sebelumnya oleh Adam Crume saya menyadari bahwa saya memiliki beberapa kesalahpahaman tentang apa artinya menjadi -hard. $\mathsf{P}$

Masalahnya adalah -sama jika ada masalah dalam dapat direduksi dengan (atau jika Anda lebih suka ). Masalah ada di luar jika tidak ada algoritma waktu polinomial untuk menyelesaikannya. Ini berarti bahwa harus ada masalah yang berada di luar tetapi tidak -hard. Jika kita mengasumsikan FACTORING berada di luar , maka jawaban Peter Shor menunjukkan bahwa FACTORING bisa menjadi masalah. $\mathsf{P}$ $\mathsf{P}$ $\mathsf{L}$ $\mathsf{NC}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$ $\mathsf{P}$

Adakah masalah yang diketahui (alami atau buatan) yang diketahui berada di luar tetapi tidak menjadi -hard? Bagaimana dengan asumsi yang lebih lemah dari asumsi anjak piutang? Apakah ada nama untuk kelas kompleksitas ini? $\mathsf{P}$ $\mathsf{P}$

cc.complexity-theory complexity-classes Artem Kaznatcheev
sumber

Jawaban:

Jika maka tidak ada set yang jarang (bahkan yang tidak dapat dihitung) dapat menjadi . $\mathsf{P} \neq \mathsf{L}$ $\mathsf{P\text{-}hard}$

Kesalahpahaman datang dari pemikiran tentang kelas kompleksitas (dan masalah komputasi) sebagai menciptakan tatanan linier yang tidak benar. Menggunakan kata "kekerasan" untuk masalah dapat digunakan untuk menyelesaikan masalah lain di kelas juga berkontribusi pada kesalahpahaman. Lowerbound untuk suatu masalah (yaitu tidak berada dalam kelas kompleksitas) tidak menyiratkan bahwa masalahnya sulit untuk kelas (yaitu dapat digunakan untuk memecahkan masalah lain di kelas). Saya tidak tahu apakah ada terminologi alternatif yang lebih baik untuk "kekerasan" yang sedang digunakan saat ini, salah satu yang telah digunakan dalam beberapa dekade sebelumnya adalah "universalitas" (yang, IMHO, menyatakan konsep lebih setia, dan kemudian kita bisa menggunakan "kekerasan" karena tidak berada di kelas, tetapi mengubah terminologi yang sudah mapan sangat sulit).

Kaveh
sumber

beberapa diagram Euler yang pernah saya lihat tentang kelas kompleksitas juga memberi makan kesalahpahaman kedua bagi saya, yang menurut saya menyebabkan kebingungan saya tentang kekerasan-X.

Artem Kaznatcheev

@ Art, ya, itu juga merupakan faktor. Inilah yang saya lakukan di kelas: Saya menyebutkan pengurangan dan bawah yang tidak ada bandingannya , berharap ini akan membantu siswa menghindari berpikir bahwa semuanya secara linear.

\mod p

$\mod p$

\mod q

$\mod q$

A C^{0}

$\mathsf{AC^0}$

Kaveh

bagian pesanan total saya memiliki lebih sedikit masalah dengan. Secara khusus, saya pikir NP dan CoNP cukup baik untuk menunjukkan bahwa kita tidak boleh berpikir kelas kompleksitas memiliki urutan total.

Artem Kaznatcheev

@ Artem, poin bagus (meskipun kami tidak dapat membuktikan bahwa mereka berbeda). Saya pikir bagian dari alasan terminologi adalah kurangnya lowerbounds yang masuk akal, kami tidak memiliki lowerbound yang baik untuk SAT, tetapi kami berpikir bahwa itu sulit untuk diselesaikan karena itu universal, tetapi kata "universal" tidak berikan perasaan kesulitan yang sama seperti yang "sulit" lakukan, terutama bagi yang bukan ahli. Tetapi itu menciptakan masalah karena walaupun orang dapat berargumentasi bahwa universalitas suatu masalah menyiratkan bahwa masalah itu sulit untuk dipecahkan, kesulitan untuk memecahkan suatu masalah tidak menyiratkan bahwa masalah itu bersifat universal.

Kaveh

yaitu masalah universal itu sulit (setidaknya sama sulitnya dengan masalah apa pun di kelas), tetapi masalah sulit tidak harus bersifat universal.

Kaveh

Saya pikir Anda dapat membangun satu set tidak dalam yang bukan oleh argumen gaya Ladner. Inilah contoh spesifik. $P$ $P$

Dalam makalahnya "Pendekatan Seragam untuk Mendapatkan Set Diagonal di Kelas Kompleksitas" (Theor. Comp. Sci. 18, 1982), Schöning membuktikan hal-hal berikut:

Teorema Misalkan , , dan adalah kelas kompleksitas yang dapat secara rekursif dan ditutup dengan variasi terbatas. Lalu ada himpunan sehingga , , dan jika dan tidak sepele (set kosong atau semua string) maka adalah polytime, banyak yang dapat direduksi menjadi . $A_1 \notin C_1$ $A_2 \notin C_2$ $C_1$ $C_2$ $A$ $A \notin C_1$ $A \notin C_2$ $A_1 \in P$ $A_2$ $A$ $A_2$

Untuk menerapkan ini, set menjadi himpunan kosong, dan menjadi -Lengkap bawah pengurangan polytime, mengatur adalah himpunan -Hard set yang berada di , mengatur . Set kosong tidak boleh -hard (definisi -hardness untuk suatu bahasa mensyaratkan bahwa setidaknya ada satu instance dalam bahasa dan satu instance tidak dalam). jelas tidak dalam . The dan dapat diverifikasi untuk memenuhi kondisi di atas (mirip dengan bagaimana Schoening melakukannya untuk $A_1$ $A_2$ $EXP$ $C_1$ $P$ $EXP$ $C_2 = P$ $P$ $P$ $A_2$ $C_2$ $C_1$ $C_2$ $NP$ -Lengkap set; lihat juga pertanyaan terkait ini ). Jadi kita mendapatkan yang bukan masalah -Hard di , dan bahwa tidak dalam . Tetapi karena dan adalah nontrivial, adalah banyak yang dapat direduksi menjadi set -Lengkap, jadi ia dalam . Karena itu, khususnya, juga tidak bisa -keras. $A$ $P$ $EXP$ $A$ $P$ $A_1 \in P$ $A_2$ $A$ $EXP$ $EXP$ $A$ $P$

Dalam argumen di atas, pembatasan untuk masalah -hard dalam diperlukan untuk memastikan presentabilitas rekursif, karena masalah P-hard secara keseluruhan tidak dapat ditampilkan secara rekursif dan bahkan tidak dapat dihitung . Sekarang, contoh "alami" dari ini adalah cerita yang berbeda ... $P$ $EXP$

Ryan Williams
sumber

Aku seperti bagaimana ini berjalan melalui bahkan jika . Kecuali saya salah paham akan sesuatu.

L = P

$L = P$

Artem Kaznatcheev

@ Artem: Jika Anda menganggap kekerasan di bawah reducibilitas ruang log, maka setiap bahasa nontrivial adalah L-hard. Oleh karena itu, jika L = P, tidak ada bahasa di luar P adalah P-hard di bawah reducibilitas ruang log.

Tsuyoshi Ito

Cara lain untuk menghasilkan masalah yang berada di luar P tetapi tidak P-hard adalah dengan mengambil masalah lengkap untuk kelas yang tidak sebanding dengan P. Katakanlah kelas X tidak dapat dibandingkan dengan P, dalam arti bahwa tidak ada bagian dari yang lain. Maka masalah X-complete harus di luar P (jika tidak P akan menyertakan X) dan bukan P-keras (jika tidak X akan menyertakan P).

Saya mencoba memikirkan beberapa kelas yang tidak dapat dibandingkan dengan P, tetapi P adalah kelas yang cukup kuat, jadi tidak terlalu banyak kelas seperti itu. Sebagai contoh, RNC dan QNC mungkin tidak ada bandingannya dengan P. DSPACE ( ) mungkin juga tidak ada bandingannya dengan P. PolyL tidak ada bandingannya dengan P, tetapi tidak memiliki masalah lengkap dalam pengurangan logspace. $\log^2$

Robin Kothari
sumber

Menurut pendapat saya, ini pertanyaan yang hampir sama diutarakan secara berbeda, dan itu belum tentu cara untuk menjawab pertanyaan. Faktanya, bahasa A tidak dalam P atau P-hard jika dan hanya jika kelas bahasa yang direduksi menjadi A tidak sebanding dengan P (anggaplah gagasan reducibilitas favorit Anda). Sepanjang pertanyaan saat ini menyangkut, saya pikir itu lebih mungkin berguna dalam arah yang berlawanan; yaitu, ini adalah cara lain untuk menginterpretasikan jawaban atas pertanyaan saat ini.

Tsuyoshi Ito