Jika batas bawah suatu masalah bersifat eksponensial, maka apakah itu NP?

Dengan asumsi bahwa kita memiliki masalah dan kami menunjukkan bahwa batas bawah untuk menyelesaikan adalah .$p$$p$$\mathcal{\Omega}(2^n)$

• dapat batas bawah menyiratkan masalah dalam ?$\mathcal{\Omega}(2^n)$$NP$

Tidak. Misalnya, masalah penghentian memiliki batas bawah , tetapi tidak dalam NP (karena tidak dapat dihitung).$\Omega(2^n)$

Teorema hierarki waktu nondeterministik menunjukkan bahwa masalah lengkap NEXP adalah contoh lain (dengan berpotensi diganti oleh fungsi eksponensial yang lebih kecil ).$2^n$$c^{n^\epsilon}$

NP adalah batas atas kompleksitas masalah.

Tidak. Pertama, seperti yang Yuval tunjukkan , masalahnya bisa jauh lebih sulit daripada batas bawah yang telah Anda buktikan.

Kedua, bahkan jika masalah membutuhkan waktu untuk menyelesaikan, kita tidak tahu bagaimana ini berhubungan dengan . Mungkin , dalam hal ini ada masalah dalam tentu saja tidak ada di oleh teorema hierarki waktu. Tetapi bahkan jika , mungkin saja masalahnya membutuhkan ruang eksponensial sehingga tidak ada di .$\Theta(2^n)$$\mathbf{NP}$$\mathbf{P}=\mathbf{NP}$$\mathrm{TIME}[\Omega(2^n)]$$\mathbf{NP}$$\mathbf{P}\neq\mathbf{NP}$$\mathbf{NP}$

Algoritme terbaik yang kami tahu untuk - masalah lengkap membutuhkan waktu eksponensial tetapi Anda tidak boleh berasumsi bahwa "di " berarti "perlu waktu eksponensial" atau sebaliknya.$\mathbf{NP}$$\mathbf{NP}$