Apakah ada teori yang menggabungkan teori kategori / aljabar abstrak dan kompleksitas komputasi?

Kategori teori dan aljabar abstrak berhubungan dengan cara fungsi dapat dikombinasikan dengan fungsi lainnya. Teori kompleksitas berkaitan dengan seberapa sulit suatu fungsi dikomputasi. Aneh bagi saya bahwa saya belum pernah melihat orang yang menggabungkan bidang studi ini, karena mereka tampak seperti pasangan alami. Adakah yang pernah melakukan ini sebelumnya?

Sebagai contoh yang memotivasi, mari kita lihat monoids. Sudah diketahui bahwa jika suatu operasi adalah monoid, maka kita dapat memparalelkan operasi tersebut.

Sebagai contoh di Haskell, kita dapat dengan sepele mendefinisikan bahwa penambahan adalah monoid di atas bilangan bulat seperti ini:

instance Monoid Int where
    mempty = 0
    mappend = (+)

Sekarang jika kita ingin menghitung jumlah 0 hingga 999, kita dapat melakukannya secara berurutan seperti:

foldl1' (+) [0..999]

atau kita bisa melakukannya secara paralel

mconcat [0..999] -- for simplicity of the code, I'm ignoring that this doesn't *actually* run in parallel

Tetapi memparalelkan monoid ini masuk akal hanya karena pemetaan berjalan dalam waktu yang konstan. Bagaimana jika ini bukan masalahnya? Daftar, misalnya, adalah monoids di mana mappend tidak menjalankan waktu tidak konstan (atau spasi!). Saya menduga inilah sebabnya tidak ada fungsi paralel standar mconcat di Haskell. Implementasi terbaik tergantung pada kompleksitas monoid.

Sepertinya harus ada cara yang mudah untuk menggambarkan perbedaan antara kedua monoids ini. Kami kemudian dapat membuat anotasi kode kami dengan perbedaan-perbedaan ini dan membuat program secara otomatis memilih algoritma terbaik untuk digunakan tergantung pada kompleksitas monoid.

[Kompleksitas komputasi dan teori kategori] tampak seperti pasangan alami.

Mengingat keunggulan kompleksitas komputasi sebagai bidang penelitian, jika mereka teman akrab alami, mungkin seseorang sudah akan mengeluarkan koneksi?

Spekulasi liar. Biarkan saya menghibur pembaca dengan pemikiran tentang mengapa rendering kompleksitas komputasi yang sulit. Dapat diperdebatkan, kluster konsep utama dalam teori kategori berpusat di sekitar konstruksi / sifat universal (dengan aparatus yang terkait dengan fungsi-fungsi, transformasi alami, tambahan, dan sebagainya). Jika kita dapat menunjukkan bahwa konstruksi matematika memiliki sifat universal, itu memberikan banyak wawasan. Jadi jika kita menginginkan pendekatan kategoris pada kompleksitas komputasi, kita perlu menemukan kategori yang sesuai dan menunjukkan bagaimana konsep kunci teori kompleksitas (misalnya LOGSPACE atau NP-hardness) dapat diberikan oleh konstruksi universal menggunakan kategori tersebut. Ini belum dilakukan, dan saya pikir ini karena ini adalah masalah yang sangat sulit.

$T = T_1 \oplus T_2 \otimes T_3$$T_i$$\oplus, \otimes$¹ . Sebagai gantinya, kami membuat TM dengan menetapkan dua komponen mereka secara terpisah: kontrol (FSM) dan pita. Baik kontrol maupun pita tidak memiliki aljabar yang baik.

Mari kita lihat rekamannya terlebih dahulu. Ada beberapa cara alami untuk membuat kaset, tidak ada satupun yang berfungsi untuk deskripsi komposisi TM.

• Rekatkan keduanya seperti penambahan ordinal. Ini bukan gagasan yang tepat, karena kaset tidak terbatas dan dengan menyatukannya seperti penambahan ordinal kita mendapatkan objek ganda tak terbatas yang melampaui kemampuan terbatas, yang mengarah ke perhitungan / hiperkomputasi tak terbatas, yang menarik secara matematis tetapi tidak sesuai dengan matematika perhitungan yang layak.

• Tempelkan keduanya secara paralel , mis. Dua mesin 3-kepala berubah menjadi mesin 6-kepala. Ini tidak memberi tahu kami bagaimana mesin komponen berinteraksi satu sama lain.

• Kaset interleave. Satu masalah dengan pendekatan ini adalah bahwa tidak jelas apa yang mungkin terjadi interleaving kanonik, jika ada. Selain itu, interleaving akan 'membingungkan' kontrol yang ada, yang cenderung disetel secara halus ke arah tata letak kaset tertentu. Jadi kami tidak dapat menggunakan kembali kontrol secara langsung.

$\pi$

Semua dalam semua, kita cukup jauh membentuk perlakuan aljabar / kategoris besar kompleksitas komputasi, dan kita akan memerlukan beberapa kemajuan konseptual untuk sampai ke sana.

$\lambda$$\pi$$\lambda$$\pi$$\alpha$$\lambda$$\pi$

Ini jawaban tentang isomorphisms antara bahasa resmi menggabungkan hasil aljabar dari teori kode dengan gagasan-gagasan dari teori kategori untuk menyelidiki kemungkinan pengertian tentang kesetaraan dan isomorfisme antara bahasa formal dan kelas kompleksitas.

Interpretasi saya sendiri atas hasil ini adalah bahwa titik sinkronisasi dalam kata-kata berbeda untuk transduser non-deterministik deterministik dan tidak ambigu, dan bahkan berbeda antara transduser deterministik maju dan transduser mundur deterministik. Mengambil perspektif titik sinkronisasi ini memungkinkan untuk menghubungkan hasil ini ke bahasa pushdown yang tampak, dan menimbulkan pertanyaan apakah mereka juga harus mempertimbangkan pemisah sederhana (seperti spasi atau koma) selain panggilan dan pengembalian. (Dugaan saya adalah bahwa pemisah dapat ditiru oleh panggilan kembali + gabungan, tetapi karena mereka memerlukan dua simbol, bukan satu, tidak jelas bagi saya apakah ini cukup. Mungkin juga ada bahasa yang hanya memiliki pemisah, tetapi tidak ada panggil atau kembalikan simbol.)