Penjelasan kelas P dan NP melalui lambda-calculus

Dalam pengantar dan penjelasan kompleksitas P dan NP sering diberikan melalui mesin Turing. Salah satu model perhitungan adalah lambda-calculus. Saya mengerti, bahwa semua model perhitungan adalah setara (dan jika kita dapat memperkenalkan apa pun dalam istilah mesin Turing, kita dapat memperkenalkan ini dalam istilah model komputasi apa pun), tetapi saya tidak pernah melihat ide penjelasan kelas kompleksitas P dan NP melalui lambda-calculus . Adakah yang bisa menjelaskan pengertian kelas kompleksitas P dan NP tanpa mesin Turing dan hanya dengan kalkulus lambda sebagai model perhitungan.

cc.complexity-theory complexity-classes turing-machines lambda-calculus Simpleks
sumber

Kekuatan komputasi mereka setara hanya untuk fungsi-fungsi di atas bilangan asli, bukan tipe yang lebih tinggi atau pengaturan lainnya.

Kaveh

Kelengkapan Turing kadang-kadang merupakan konsep yang lebih teoretis untuk menunjukkan koneksi tetapi "konversi" yang lebih diterapkan antara sistem lengkap TM tidak selalu benar-benar dilakukan dalam praktiknya yaitu terkadang lebih banyak tentang bukti keberadaan ...

vzn

Jawaban:

Turing- Machines dan $\lambda$ -calculus hanya setara dengan fungsi $\mathbb{N} \rightarrow \mathbb{N}$ dapat mereka tentukan.

Dari sudut pandang kompleksitas komputasi mereka tampaknya berperilaku berbeda. Alasan utama orang menggunakan mesin Turing dan bukan $\lambda$ -kalkulus untuk alasan kompleksitas adalah bahwa menggunakan $\lambda$ -kalkulus secara naif mengarah pada langkah-langkah kompleksitas yang tidak realistis, karena Anda dapat menyalin istilah (ukuran sewenang-wenang) secara bebas dalam langkah-langkah pengurangan $\beta$ tunggal , misalnya $(\lambda x.xxx)M \rightarrow MMM.$ Dengan kata lain, langkah reduksi tunggal dalam $\lambda$ -kalkulus adalah model biaya yang buruk. Sebaliknya, langkah-langkah pengurangan mesin Turing tunggal bekerja sangat baik (dalam arti menjadi prediktor yang baik untuk menjalankan-waktu program dunia nyata).

Tidak diketahui bagaimana sepenuhnya memulihkan teori kompleksitas berbasis mesin Turing konvensional dalam $\lambda$ -kalkulus. Dalam terobosan baru - baru ini (2014), Accattoli dan Dal Lago berhasil menunjukkan bahwa kelas besar kompleksitas waktu seperti $P$ , $NP$ dan $EXP$ dapat diberikan formulasi $\lambda$ kalkulus alami . Tetapi kelas yang lebih kecil seperti $O(n^2)$ atau $O(n \, log\, n)$ tidak dapat disajikan dengan menggunakan teknik Accattoli / Dal Lago.

Bagaimana memulihkan kompleksitas ruang konvensional menggunakan $\lambda$ -calculus tidak diketahui.

Martin Berger
sumber

Saya merasa perlu mengklarifikasi di sini: tidak ada "teknik" khusus yang digunakan oleh Accattoli dan Dal Lago untuk "menyajikan" kelas waktu. Presentasi adalah "naif" satu: mendefinisikan

sebagai kelas bahasa decidable oleh

-istilah di

-reduction langkah, di bawah setiap strategi pengurangan standar ( misalnya paling kiri -paling luar). Accattoli dan Dal Lago menunjukkan, menggunakan teknik yang berasal dari logika linier, bahwa ada polinom

sehingga

λ T I M E (f (n))

$\lambda TIME(f(n))$

λ

$\lambda$

f (n)

$f(n)$

β

$\beta$

p

$p$

λ T I M E (f (n)) = T I M E (p (f (n))

$\lambda TIME(f(n))=TIME(p(f(n))$

Damiano Mazza

@ DamianoMazza Ya itu benar, yang saya maksud adalah bahwa saya tidak berpikir teknik yang digunakan untuk menunjukkan hasil ini dapat digunakan untuk menunjukkan misalnya

λ T I M E (n^{2}) = T I M E (n^{2})

$\lambda TIME(n^2) = TIME(n^2)$

Martin Berger

Ok aku paham. Sebenarnya, tebakan saya adalah bahwa

: kelas kompleksitas seperti

atau

tidak kuat , kita tidak bisa mengharapkan mereka stabil di bawah perubahan dalam model komputasi (ini terkenal kasusnya bahkan jika kita tetap menggunakan mesin Turing, misalnya single-tape vs multi-tape).

λ T I M E (n^{2}) \neq T I M E (n^{2})

$\lambda TIME(n^2)\neq TIME(n^2)$

T I M E (n^{2})

$TIME(n^2)$

T I M E (n \log n)

$TIME(n\log n)$

Damiano Mazza

@ DamianoMazza Saya setuju, demikian juga untuk ukuran alfabet yang dipilih. Tetapi sebuah algoritma yang berjalan di

pada mesin

-tape dapat disimulasikan dalam

pada mesin 1-tape, sebuah ledakan kuadratik sederhana. Apa heboh terjemahan Accattoli and Dal Lago's saat ini? Saya tidak ingat apakah mereka secara eksplisit menyatakannya.

f (n)

$f(n)$

n

$n$

5 k f^{2} (n)

$5kf^2(n)$

Martin Berger

@Jake Makalah yang dikutip ini membahas normalisasi beta (lihat halaman dua). Hasil yang serupa sudah dikenal untuk bentuk reduksi lain, seperti reduksi lemah (yaitu, call-by-value) - lihat Dal Lago & Martini, 2008 (dibahas dalam makalah itu dan di cstheory.stackexchange.com/a/397/989 ).

Blaisorblade

Saya menempelkan sebagian jawaban yang saya tulis untuk pertanyaan lain :

Kompleksitas Komputasi Implisit bertujuan untuk mengkarakterisasi kelas kompleksitas dengan menggunakan bahasa khusus. Hasil pertama seperti Teorema Bellantoni-Cook dinyatakan dalam hal fungsi rekursif, tetapi hasil yang lebih baru menggunakan kosakata dan teknik -kalkulus. Lihat pengantar singkat ini untuk Kompleksitas Komputasi Tersirat untuk lebih banyak dan petunjuk, atau proses dari lokakarya DICE . $\mu$ $\lambda$

Ada ada penokohan (setidaknya) dengan menggunakan kalkulus. $\mathsf{FP}$ $\lambda$

Bruno
sumber

$\mathbb{P}$ $\mathbb{NP}$

Beberapa penokohan lebih lanjut dari kelas kompleksitas komputasi dalam hal kompleksitas algoritmik (Kolmogorov-Solomonov) dapat ditemukan (misalnya) di sini dan di sini .

Nikos M.
sumber