Lingkup pembatas bukti alami

Penghalang bukti alami dari Razborov dan Rudich menyatakan bahwa di bawah asumsi kriptografi yang kredibel orang tidak dapat berharap untuk memisahkan NP dari P / poli dengan menemukan sifat kombinatorial dari fungsi yang konstruktif, besar, dan bermanfaat. Ada beberapa hasil terkenal yang berhasil menghindari penghalang. Ada juga beberapa makalah yang membahas kemungkinan celah untuk tiga kondisi, seperti hasil Chow yang menunjukkan penghalang sensitif terhadap pelanggaran yang lemah terhadap jumlah besar, dan makalah terbaru Chapman dan Williamsmenyarankan bagaimana cara berpotensi menghindari penghalang dengan merelaksasi kondisi kegunaan. Pertanyaan saya adalah apakah ada contoh, atau bahkan kemungkinan, untuk menghindari penghalang bukti alam bukan dengan melanggar konstruktifitas, kebesaran, atau kegunaan, tetapi dengan jatuh sepenuhnya di luar cakupannya. Artinya, sama sekali tidak jelas bagi saya mengapa setiap metode pembuktian yang potensial harus didasarkan pada penemuan "properti" kombinatorial dan kemudian mempartisi semua fungsi menjadi fungsi yang memenuhi dan tidak memenuhi properti. Mengapa kerangka kerja operasi ini berlaku untuk semua bukti yang mungkin, dan jika tidak maka akan seperti apa jenis bukti lainnya?

Biarkan menjadi fungsi, dan biarkan C menjadi kelas algoritma yang bekerja pada irisan terbatas f . Setiap sirkuit yang lebih rendah terikat apapun adalah bukti bahwa f ∉ C , untuk beberapa f dan beberapa C . Pertimbangkan "properti kombinatorial dari Boolean fungsi" P f , sehingga$f: \{0,1\}^* \rightarrow \{0,1\}$$C$$f$$f \notin C$$f$$C$${\cal P}_f$

dan P f (g)=0untuk semuag≠f.${\cal P}_f(f) = 1$${\cal P}_f(g) = 0$$g \neq f$

Sebuah bukti bahwa adalah bukti bahwa P f adalah berguna melawan C , dalam terminologi Razborov dan Rudich. Artinya, "kegunaan" sama sekali tidak dapat dihindari - tidak ada cara untuk "berada di luar cakupannya." Jika Anda telah membuktikan sirkuit dengan batas bawah sama sekali, Anda telah memberikan beberapa properti yang bermanfaat.$f \notin C$${\cal P}_f$$C$

Perhatikan bahwa, jika , maka P f juga konstruktif, dalam terminologi Razborov dan Rudich. Jadi untuk fungsi f dihitung dalam E tapi tidak di (katakanlah) P / p o l y , constructivity juga akan berlaku untuk setidaknya satu properti dari fungsi Boolean yang berguna terhadap P / p o l y .$f \in TIME[2^{O(n)}]$${\cal P}_f$$f$$E$$P/poly$$P/poly$

Jadi, Razborov dan Rudich lebih mendasar daripada yang Anda bayangkan.

Anda benar: teorema bukti alami adalah tentang sifat alami (dan hanya secara informal tentang bukti). Razborov sendiri menulis dua makalah sekitar waktu yang sama melihat ke kelas bukti formal dan kompleksitas batas bawah:

• Aritmatika Terikat dan Batas Bawah dalam Kompleksitas Boolean , 1995
• Unprovability dari Batas Bawah pada Ukuran Sirkuit di Fragmen Tertentu dari Aritmatika Terbatas , 1995

Yang pertama mempelajari formalisasi bukti batas bawah yang ada dalam fragmen lemah aritmatika (batas atas pada kekerasan membuktikan teori kompleksitas batas bawah).

$\mathsf{P} \neq \mathsf{NP}$$ZFC$$ZF$$PA$$PV$$PV$$\mathsf{P}$

$PV$$\mathsf{P} \neq \mathsf{NP}$

$PV$

$\mathsf{P} \neq \mathsf{NP}$$\mathsf{P}$