Pertanyaan yang diberi tag p-vs-np

Saya baru-baru ini memikirkan bukti berikut bahwa L = P menyiratkan P = NP. Misalkan L = P. Biarkan A menjadi masalah di NP. Dengan definisi verifikasi NP, setiap solusi positif untuk A memiliki saksi yang dapat diverifikasi dalam waktu polinomial. Karena P = L, solusi yang sama dapat...

Saya yakin pasti ada yang salah dengan alasan berikut karena jika tidak banyak penelitian P vs NP akan dikurangi tetapi saya tidak dapat menentukan kesalahan saya: Untuk bilangan bulat tetap k>0k>0k>0 menetapkan Bk:={⟨φ⟩|φis a wff of ZF and has a proof of length≤k|φ|k}Bk: ={⟨φ⟩|φadalah wff...

Mungkin saya kehilangan sesuatu yang jelas, tetapi mungkinkah itu P = co-NP ⊊⊊\subsetneqNP atau sebaliknya? Perasaan saya adalah bahwa harus ada beberapa teorema yang mengesampingkan kemungkinan