Apakah "minimal", yaitu apakah menyiratkan adalah -hard?

Misalkan adalah masalah keputusan yang dapat ditentukan.$\Pi$

Apakah menyiratkan adalah -Hard?$\Pi\not \in NP$$\Pi$$NP$

Sunting: jika kita asumsikan ada maka kita selesai. Bisakah kita menyangkal klaim tanpa asumsi yang tidak diketahui?$\Pi\in coNP\setminus NP$

Jika Anda berasumsi bahwa maka setiap masalah yang diselesaikan coNP memberikan contoh tandingan. Saya kira orang dapat menyangkal dugaan Anda tanpa syarat.$\mathsf{NP}\neq\mathsf{coNP}$

Jika maka$P=NP$

$\Pi \not\in NP$
$\implies$
$P=NP$ dan bukanlah bahasa kosong atau bahasa lengkap adalah -hard.$\Pi$
$\implies$
$\Pi$$NP$

Biarkan menunjukkan hasil dari meletakkan 1 di akhir paling signifikan dan kemudian menguraikan hasilnya sebagai integer dalam biner.$\operatorname{int}(s)$$s$

Jika maka untuk setiap subset dari yang tidak dalam , tidak ada dalam NP karena terlalu keras, dapat ditentukan jika dan hanya jika adalah, dan bukan NP-keras bahkan sehubungan dengan pengurangan Turing karena untuk setiap ikatan polinomial, hanya ada banyak kemungkinan polynomally untuk subset dari bahasa yang terdiri dari unsur-unsur yang sesuai dengan batas panjang, sehingga seseorang dapat mencoba cari pengurangan dengan masing-masing keputusan .$P\neq NP$ $S$$\{0,1\}^*$$\operatorname{NTIME}$$\left(2^{O\left(2^n\right)}\right)$
$\{111 \ldots [2^{\operatorname{int}(n)} \text{ of them}] \ldots 111 : n\in S\}$$S$$S$

Kelengkapan untuk suatu kelas berarti sifatnya universal untuk kelas tersebut, yaitu masalah lain di dalam kelas dapat diselesaikan dengan menggunakannya. Jika ada masalah yang sulit di kelas maka semua masalah universal untuk kelas juga akan sulit. Tetapi kebalikannya tidak berlaku: kesulitan tidak menyiratkan universalitas. Misalnya fakta bahwa masalah tidak dapat diselesaikan dalam waktu nondeterministik polinomial tidak menyiratkan bahwa itu adalah NP-lengkap (yaitu universal untuk NP).

Untuk NP: jika P = NP semua masalah kecuali yang sepele akan lengkap untuk NP (dalam pengurangan Karp). Jadi anggaplah P adalah subset NP yang tepat (atau gunakan gagasan reduksi yang lebih lemah seperti AC0).

Pertimbangkan bahasa unary yang berada di luar NP. (Ini adalah latihan yang mudah untuk menunjukkan ada bahasa unary kesulitan sewenang-wenang.) Bahasa tidak dapat lengkap untuk NP oleh teorema Mahoney.