NP vs ko-NP dan logika orde kedua

Asumsikan NP = co-NP dan polinomial membatasi panjang bukti ketidakpuasan untuk instance 3-CNF . Lalu apakah ada hasil pada bentuk apa bukti tidak memuaskan untuk panjang dapat mengambil? Yaitu secara umum, akankah bukti semacam itu harus, misalnya, menggunakan kekuatan penuh dari logika orde dua atas struktur yang tak terbatas (saya sadar bahwa proposisi untuk membuktikan - bahwa formula tidak memuaskan dapat diekspresikan dalam logika orde dua melalui struktur terbatas tetapi langkah-langkah perantara dalam bukti untuk sampai ke yang mungkin memerlukan alasan atas struktur tak terbatas).x x ≤ p ( x ) $p(x)$$x$$x$$\leq p(x)$

Karena tidak ada sistem inferensi yang efektif, lengkap, dan logis untuk logika tingkat kedua, mungkinkah menggunakan hasil seperti itu untuk membuktikan NP co-NP?$\neq$

Jika ada pps optimal (pps = sistem bukti proposisional , pps optimal adalah pps yang dapat p-mensimulasikan sistem bukti lainnya) maka pps EF (Extended Frege) diperkuat dengan aksioma proposisional yang menyatakan tingkat kesehatan sistem bukti proposisional optimal akan optimal. Secara umum, EF + Tingkat Kesehatan pps P dapat mensimulasikan P untuk P. apa pun. Jadi EF memiliki semacam sifat umum sehingga Anda tidak perlu mengubah logika atau struktur pps yang mendasarinya, tetapi tambahkan saja aksioma proposisional untuk mendapatkan apa pun. pps kuat sewenang-wenang.

Khususnya, jika ada pps super (pps yang memiliki bukti ukuran polinom untuk semua tautologi) maka EF + Soundness dari pps itu akan menjadi pps super. Perhatikan bahwa setara dengan keberadaan super pps.$NP = coNP$

Kesehatan pps P adalah formula urutan proposisional yang menyatakan bahwa jika adalah bukti dalam P untuk , maka benar.φ $\pi$$\varphi$$\varphi$

Dalam musim panas, tidak perlu keluar dari logika proposisional.

ps: Perhatikan bahwa semua pps efektif berdasarkan definisi, pps memiliki verifier waktu polinomial, dan oleh karena itu teorema-teorema-nya dapat dihitung secara komputasi. berarti ada super pps untuk formula proposisional . Menjadi proposisional penting di sini. Kita tahu bahwa tidak ada hal seperti itu untuk logika yang lebih kuat tetapi tidak adanya mereka tampaknya tidak memiliki efek pada vs .N P c o N $NP=coNP$$NP$$coNP$