Mengurangi pertanyaan ambang batas menjadi pertanyaan keterbatasan

Biasanya lebih mudah untuk berpikir tentang kalkulus di mana batasannya adalah keterbatasan perhitungan daripada ambang batas seperti "dapat dihitung dalam jumlah waktu polinomial".

Dalam teori bahasa formal misalnya, alih-alih menggunakan $\exists n. x^{n+1} = x^n$ untuk mengkarakterisasi monoïd aperiodik, lebih mudah untuk menggunakan kata-kata tak terbatas sehingga $x^{\omega+1} = x^{\omega}$ .

Dalam teori kompleksitas, satu-satunya teknik yang saya tahu yang terkait adalah trik padding misalnya menghubungkan masalah P vs NP ke EXPTIME vs NEXPTIME. Tetapi pertanyaan tak terbatas yang setara dengan kompleksitas akan menjadi pertanyaan kompabilitas.

Apakah ada beberapa hasil yang menghubungkan kompleksitas dengan pertanyaan komputabilitas menggunakan beberapa pengkodean sehingga ambang sumber daya dari teori kompleksitas menjadi pertanyaan keterbatasan komputasi dalam teori komputasi?

Sipser membuktikan bahwa tidak ada paritas tak terbatas yang dapat dihitung oleh sirkuit (tak terbatas) dengan kedalaman konstan apa pun, yang dapat Anda lihat sebagai pemanasan terhadap hasil bahwa PARITY tidak dalam .$AC^0$

Ada juga beberapa hasil dan upaya pada bukti batas bawah dalam kompleksitas bukti menggunakan model tidak standar (beberapa hasil dari Ajtai dan Krajicek. Lihat esp. Krajiceks '"Memaksa dengan Variabel Acak dan Kompleksitas Bukti," tersedia dari Cambridge Press, tetapi juga konsep tersedia online ). Ide dasarnya adalah untuk membangun model aritmatika yang tidak standar di mana pernyataan salah dalam model (daripada "benar, tetapi tanpa bukti pendek"), dan kemudian, dari sifat-sifat model, menyimpulkan bahwa urutan terbatas yang sesuai pernyataan tidak memiliki bukti ukuran polinomial dalam beberapa sistem bukti.

Saya tidak yakin, tetapi kesan saya adalah bahwa seringkali hasil-hasil ini semacam "menyembunyikan asimptotik di bawah kap" sehingga tidak begitu banyak pengurangan dari ambang batas menjadi keterbatasan karena itu adalah bahasa matematika baru di mana "salah" di bahasa baru sesuai dengan "tanpa bukti pendek" dalam bahasa lama. Itu bukan untuk mengatakan bahwa bahasa baru tidak memberikan sudut pandang baru yang bermanfaat, tapi saya tidak yakin apakah itu yang Anda cari.

Bidang kompleksitas deskriptif, dan kompleksitas implisit dapat dipandang sebagai mengambil pendekatan semacam ini. Keduanya mengubah batasan sumber daya (seperti atau ) menjadi kemampuan mengungkapkan masalah dalam formalisme logis (untuk kompleksitas deskriptif) atau dalam bahasa pemrograman tertentu (untuk kompleksitas implisit).N $P$$NP$

Jadi itu bukan per se terkait dengan perhitungan yang tak terbatas, tetapi lebih kepada ekspresibilitas masalah dalam model yang diberikan. Namun itu dekat dalam arti bahwa itu mengubah masalah kuantitatif menjadi masalah kualitatif.