Apakah ada sistem tipe, yang membatasi istilah lambda dengan istilah yang termasuk dalam kelas kompleksitas? Seperti istilah yang bisa diketik dalam teori secara ketat di dalam kelas kompleksitas? Atau apakah itu tidak mungkin sama sekali?
Saya menemukan ada banyak studi tentang ekspresibilitas teori jenis, seperti terminasi, polinomial diperpanjang dll. Tapi apakah ada cara untuk membatasi itu ke kelas kompleksitas?
complexity-classes
type-theory
Vinothkumar Raman
sumber
sumber
Jawaban:
Kata kunci yang Anda cari adalah "Kompleksitas Komputasi Implisit". Studi lapangan untuk varian misalnya logika linier dan batas kompleksitas mereka dapat menjamin pada istilah yang mendasari derivasi.
sumber