Bukti kontradiksi untuk ketimpangan P dan NP?

Saya mencoba untuk berpendapat bahwa N bukan NP sama dengan menggunakan teorema hierarki. Ini adalah argumen saya, tetapi ketika saya menunjukkannya kepada guru kami dan setelah deduksi, ia mengatakan bahwa ini bermasalah di mana saya tidak dapat menemukan alasan kuat untuk menerimanya.

Kami memulai dengan mengasumsikan bahwa . Kemudian ia menghasilkan yang kemudian mengikuti . Sebagai contoh, kami dapat mengurangi setiap bahasa dalam menjadi . Oleh karena itu, . Sebaliknya, teorema hierarki waktu menyatakan bahwa harus ada bahasa , itu tidak dalam . Ini akan mengarahkan kita untuk menyimpulkan bahwa adalah dalam , sementara tidak dalam , yang merupakan kontradiksi dengan asumsi pertama kami. Jadi, kami sampai pada kesimpulan bahwa . $P=NP$ $\mathit{SAT} \in P$ $\mathit{SAT} \in TIME(n^k)$ $NP$ $\mathit{SAT}$ $NP \subseteq TIME(n^k)$ $A \in TIME(n^{k+1})$ $TIME(n^k)$ $A$ $P$ $NP$ $P \neq NP$

Apakah ada yang salah dengan buktiku?

complexity-theory time-complexity p-vs-np inverted_index
sumber

Tolong, tulis sesuatu seperti $\mathit{SAT}$ bukan $SAT$ . Seperti yang ditulis Leslie Lamport dalam buku LaTeX aslinya, yang terakhir adalah singkatan dari S times A times T.

Oliphaunt - mengembalikan Monica

Lebih baik lagi, gunakan complexitypaket dan cukup menulis \SAT. (Tapi saya rasa itu tidak tersedia pada tumpukan ini.)

Oliphaunt - mengembalikan Monica

@Oliphaunt Mengapa tidak menyarankan edit ketika Anda dapat meningkatkan posting? Meskipun saya harus mengatakan bahwa di sini perbedaannya (jika ada) jauh lebih halus daripada yang saya harapkan.

Kadal diskrit

@ Discretelizard yang sering saya lakukan, tapi kali ini "terlalu banyak pekerjaan" (saya sedang menggunakan ponsel). Memasukkan semua $ dan \ adalah pekerjaan yang rewel. Saya memilih untuk mendidik sebagai gantinya. (Keputusan ini mungkin tidak sepenuhnya rasional.)

Oliphaunt - mengembalikan Monica

Jawaban:

Kemudian ia menghasilkan $SAT \in P$ yang dengan sendirinya mengikuti $SAT \in TIME(n^k)$ .

Tentu.

Seperti berdiri, kita dapat melakukan mengurangi setiap bahasa di $NP$ ke $SAT$ . Oleh karena itu, $NP \subseteq TIME(n^k)$ .

Tidak. Pengurangan waktu polinomial tidak gratis. Kita dapat mengatakan bahwa dibutuhkan $O(n^{r(L)})$ waktu untuk mengurangi bahasa $L$ ke $SAT$ , di mana $r(L)$ adalah eksponen dalam pengurangan waktu polinomial yang digunakan. Di sinilah argumen Anda berantakan. Tidak ada $k$ hingga sehingga untuk semua $L \in NP$ kita memiliki $r(L) < k$ . Setidaknya ini tidak mengikuti dari $P = NP$ dan akan menjadi pernyataan yang jauh lebih kuat.

Dan pernyataan kuat hal ini memang bertentangan dengan waktu hirarki teorema, yang mengatakan kepada kita bahwa $P$ tidak dapat runtuh ke $TIME(n^k)$ , apalagi semua $NP$ .

orlp
sumber

Ini bukan hanya waktu untuk pengurangan itu sendiri. Anda bisa mengurangi menjadi masalah yang lebih besar. Jika saya bisa menyelesaikan X di O (n ^ 5), dan saya bisa mengurangi masalah di Y di O (n ^ 6) menjadi contoh X ukuran O (n ^ 3), maka saya membutuhkan O (n ^ 15) secara keseluruhan.

gnasher729

Yang mengherankan, argumen ini berlaku untuk masalah lengkap PTIME juga, misalnya HORNSAT, yang dapat diselesaikan dalam waktu linier (tetapi tidak semua masalah dalam P adalah waktu linier).

cody

Misalkan $\mathrm{3SAT}\in\mathrm{NTIME}[n^k]$ . Dengan versi teoretis hierarki waktu yang tidak ditentukan, untuk $r$ apa pun , ada masalah $X_r\in\mathrm{NTIME}[n^r]$ yang tidak ada dalam $\mathrm{NTIME}[n^{r-1}]$ . Ini adalah hasil tanpa syarat yang tidak bergantung pada jenis asumsi seperti $\mathrm{P}\neq\mathrm{NP}$

Pilih $r>k$ . Misalkan kita memiliki reduksi deterministik dari $X_r$ menjadi $\mathrm{3SAT}$ yang berjalan dalam waktu $n^t$ . Ini menghasilkan $\mathrm{3SAT}$ contoh dari ukuran paling $n^t$ , yang dapat diselesaikan dalam waktu paling $(n^t)^k=n^{tk}$ . Dengan pilihan $X_r$ , kita harus memiliki $tk>r-1$ , jadi $t>(r+1)/k$ . Fungsi ini tumbuh tanpa terikat dengan $r$ .

Ini berarti bahwa tidak ada terikat pada berapa lama dapat dilakukan untuk mengurangi sewenang-wenang $\mathrm{NP}$ masalah untuk $\mathrm{3SAT}$ . Bahkan jika $\mathrm{3SAT}\in \mathrm{P}$ , masih belum ada batasan berapa lama pengurangan tersebut dapat berlangsung. Jadi, khususnya, bahkan jika $\mathrm{3SAT}\in\mathrm{DTIME}[n^{k'}]$ untuk beberapa $k'$ , kita tidak dapat menyimpulkan bahwa $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k'}]$ , atau bahkan $\mathrm{NP}\subseteq\mathrm{DTIME}[n^{k''}]$ untuk beberapa $k''>k'$ .

David Richerby
sumber