Membuktikan bahwa jika

Saya benar-benar ingin bantuan Anda untuk membuktikan hal berikut.

Jika maka .P = N $\mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$\mathrm{P}=\mathrm{NP}$

Di sini, adalah kelas semua bahasa yang dapat diputuskan oleh mesin Turing nondeterministic dalam waktu polinomial dan adalah kelas dari semua bahasa yang dapat ditentukan oleh mesin Turing deterministik dalam waktu polinomial .O ( n 100 ) D T i m e ( n 1000 ) O ( n 1000$\mathrm{NTime}(n^{100})$$O(n^{100})$$\mathrm{DTime}(n^{1000})$$O(n^{1000})$

Ada bantuan / saran?

Ini solusinya menggunakan padding. Misalkan . Tetapkan bahasa baru . Setiap sesuai dengan beberapa dengan panjang . Oleh karena itu kita dapat memutuskan apakah dalam waktu non-deterministik , yaitu . Untuk memutuskan apakah , bentuk dan jalankan - algoritma deterministik waktu untukL ′ = { x 0 | x | 10 - | x | : x ∈ L } x ∈ L y ∈ L ′ | y | = | x | + ( | x | 10 - | x | ) = | x | 10$L \in \mathrm{NTime}(n^{1000})$$L' = \{x0^{|x|^{10}-|x|} : x \in L\}$$x \in L$$y \in L'$$|y| = |x| + (|x|^{10}-|x|) = |x|^{10}$| x | 1000 = | y | 100 L ′ ∈ N T i m e ( n 100 ) ⊆ D T i m e ( n 1000 ) x ∈ L y = x 0 x 10 - | x | | y | 1000 = | x | 10000 L ′ L $y \in L'$$|x|^{1000} = |y|^{100}$$L' \in \mathrm{NTime}(n^{100}) \subseteq \mathrm{DTime}(n^{1000})$$x \in L$$y = x0^{x^{10}-|x|}$$|y|^{1000} = |x|^{10000}$$L'$. Kami menyimpulkan bahwa .$L \in \mathrm{DTime}(n^{10000})$

Pecahkan masalah menjadi dua bagian:

1. Ada -lengkap bahasa di .$\mathsf{NP}$$\mathsf{NTime}(n^{1000})$
2. Jika -lengkap bahasa dalam lalu .$\mathsf{NP}$$\mathsf{DTime}(n^{1000}) \subset \mathsf{P}$$\mathsf{P}=\mathsf{NP}$

Ini adalah konsekuensi yang hampir sepele dari definisi kelengkapan NP. Jika ada bahasa dalam NP yang dapat dipecahkan dalam waktu polinomial (yang dinyatakan oleh premis), maka semuanya adalah. Cara lain untuk melihat ini adalah dengan melihat teorema Cook untuk kelengkapan NP yang mengurangi semua bahasa NP-complete menjadi pengenalan bahasa yang melibatkan SAT dan konversi mesin Turing nondeterministic menjadi SAT.