Bagaimana menilai definisi kompleksitas perhitungan real yang alami atau cocok?

Seperti yang kita ketahui, definisi kompleksitas komputasi algoritma hampir tanpa kontroversi, tetapi definisi kompleksitas komputasi real atau model komputasi atas real tidak dalam kasus seperti itu. Kita tahu model dan model Blum dan Smales dalam buku Computable Analysis. Dan tampaknya, model dalam Analisis Komputasi konsisten dengan model klasik, tetapi definisi kompleksitas komputasi real tidak dapat ditransplantasikan ke model klasik.

Dan bagaimana cara mentransplantasikan definisi kompleksitas komputasi real ke dalam model klasik?

cc.complexity-theory reference-request computability computing-over-reals computable-analysis XL _At_Here_There
sumber

Untuk pertanyaan pertama Anda, "alami" adalah gagasan yang sangat subjektif dan tergantung pada orang yang Anda tanyakan, definisi yang satu atau yang lain akan dianggap sebagai yang paling alami. Adapun "cocok", itu tergantung: model BSS tampaknya cocok untuk geometri komputasi atau geometri aljabar komputasi, dan model dalam Analisis Komputasi lebih cocok untuk ... analisis komputabel! Saya tidak mengerti pertanyaan kedua.

Bruno

@ Bruno, terima kasih atas komentar Anda, saya pikir model dalam Computable Analysis, dan tidak tahu bagaimana menerapkan definisi kompleksitas komputasi untuk perhitungan bilangan real di atas model klasik seperti Turing Machine, karena kompleksitas komputasi bilangan real atas model dalam Analisis Komputasi tergantung pada representasi itu, yaitu, input untuk perhitungan itu.

XL _At_Here_There

Anda tampaknya berpikir ada gagasan kompleksitas untuk perhitungan bilangan real yang tidak tergantung pada representasi real. Apa yang membuat Anda berpikir begitu? Ini tidak terjadi dalam kompleksitas klasik juga. Itu penting apakah Anda memiliki tape atau mesin RAM, itu penting apakah Anda mewakili grafik berdasarkan daftar adjancency atau 01-matriks, dll.

Andrej Bauer

Tetapi tidak benar bahwa kompleksitasnya tidak bergantung pada representasi. Dengan beralih ke representasi bodoh Anda selalu dapat merusak kompleksitas suatu algoritma. Pertanyaan untuk bertanya adalah: "Apa yang dimaksud dengan baik representasi dari input?" Untuk masalah diskrit, ini jauh lebih mudah dijawab daripada bilangan real, karena orang memiliki perasaan yang baik tentang apa artinya "jangan buang bit".

Andrej Bauer

model BSS tampaknya cocok untuk geometri komputasi - Lihat jawaban saya untuk pertanyaan terkait . Model RAM nyata yang digunakan oleh geometer komputasi mendahului Blum, Shub, dan Smale hampir satu dekade.

Jeffε

Jawaban:

Saya tidak begitu yakin apa pertanyaannya di sini, tetapi saya bisa mencoba sedikit untuk membersihkan kemungkinan kesalahpahaman.

$f : \mathbb{R} \to \mathbb{R}$ $\sqrt{2}$ $f$

$f : A \to B$ $A$ $(a, f(a))$ $f$

$\mathbb{R}$ $\mathbb{R}$ $\mathbb{R}$

$+$ $\times$ $-$ $/$ $|{-}|$
$x$ $k \in \mathbb{N}$ $p, q$ $|x - p/q| \leq 2^{-k}$
$x$ $y$ $x < y$
$(x_n)_n$ $|x_{n+1} - x_n| \leq 2^{-n}$ $\lim_n x_n$

Ada teorema lama (lihat pengantar makalah ini untuk referensi) yang menjelaskan mengapa kondisi ini adalah yang benar. Teorema-teorema ini juga menunjukkan bahwa dua representasi real semacam itu adalah isomorfis, yaitu, kita dapat menerjemahkannya dengan program. Ini menetapkan beberapa kriteria untuk kebenaran yang membuang ide yang salah.

Sebagai contoh, saya mendengar orang mengatakan hal-hal seperti "bilangan rasional dapat diwakili oleh informasi yang terbatas, jadi mari kita gunakan itu untuk bilangan rasional, dan bilangan irasional harus diwakili oleh informasi yang tak terbatas". Hal semacam ini tidak berfungsi karena merusak kondisi keempat di atas (pertimbangkan batas bilangan irasional - bagaimana Anda akan tahu bahwa itu konvergen ke rasional?).

Contoh lain yang dihilangkan oleh kondisi di atas adalah model Blum-Shub-Smale karena di dalamnya Anda tidak dapat menghitung batas urutan. Lebih baik untuk mengatakan bahwa model BSS bekerja pada subfield real yang dipesan secara terpisah (dihasilkan oleh parameter apa pun yang ada), bukan pada real itu sendiri.

Di antara representasi real yang benar, beberapa lebih efisien daripada yang lain, meskipun ini adalah topik yang agak sulit untuk dibahas karena bilangan real adalah objek tanpa batas. Matthias Schröder menunjukkan bahwa untuk teori kompleksitas yang masuk akal orang harus memperhatikan sifat topologis dari representasi tersebut.

Akhirnya, bagaimana kita mengukur kompleksitas peta , dengan asumsi kita memiliki representasi yang baik dari ? Karena diwakili oleh suatu fungsi, atau aliran informasi tanpa batas, atau semacamnya, kita harus menggunakan salah satu pengertian kompleksitas yang lebih tinggi . Yang mana mungkin tergantung pada representasi yang Anda gunakan. $f : \mathbb{R} \to \mathbb{R}$ $\mathbb{R}$ $x \in \mathbb{R}$

Model BSS juga merupakan model kompleksitas sirkuit yang masuk akal di mana kami menghitung operasi aritmatika. Hanya baik untuk diingat bahwa model ini bukan tentang bilangan real, tetapi tentang sesuatu yang lain.

Andrej Bauer
sumber

Terima kasih banyak atas jawaban Anda, dan banyak referensi. Saya merasa tidak nyaman dengan beberapa gagasan tentang kompleksitas komputasi, izinkan saya membaca referensi dan berpikir sejenak, dan memberikan contoh, jika saya dapat menemukan satu yang cocok untuk menjelaskan mengapa saya sangat tidak nyaman (ini terdengar lucu, Tapi pengalaman saya memberi tahu saya jika saya merasa tidak nyaman, pasti ada sesuatu yang unik)

XL _At_Here_There

Dalam pengalaman saya, merasa tidak nyaman tentang pengetahuan baru adalah pertanda baik, dan biasanya itu merupakan prasyarat untuk pencerahan.

András Salamon

Model lain yang mungkin dijelajahi adalah model RAM Layak. Ini adalah model RAM nyata yang dimodifikasi untuk perhitungan Nyata, RAM yang layak, atau model RAM yang dimodifikasi yang menggunakan operasi diskrit, dan operasi aritmatika bernilai nyata. Model ini memungkinkan untuk operasi nyata, dan terpisah, dan model Turing, dapat dipertukarkan dengannya. Model Feasible RAM memiliki ketepatan yang ditentukan dengan ketidakpastian, yang berarti bahwa memungkinkan perbandingan bilangan real hanya hingga variabel ketidakpastian 1 / (k + 1). Ini memungkinkan untuk perhitungan perkiraan. Juga, seperti yang dinyatakan Vasco Brattkaa dan Peter Hertlingb di Mesin Akses Acak yang Layak Nyata - model Turing, dan model RAM Nyata yang Layak, terkait. Semua fungsi dapat dihitung pada mesin Turing dalam waktu $<_{k}$ $O(t)$ dapat dihitung pada RAM dalam waktu , dan dalam kasus sebaliknya ada beberapa overhead untuk mesin Turing yang menghitung fungsi (jika RAM nyata menghitung fungsi dalam TM menghitung fungsi dalam .Seperti yang ditunjukkan, pertimbangan topologi bermanfaat, kita tidak tahu apakah ada konteks topologi yang dikembangkan untuk model perhitungan ini yang memungkinkan untuk perhitungan nyata - yang memiliki ketidakpastian dalam presisi. $O(t)$ $O(t)$ $O(t^{2}log(t)log(log(t)))$

pengguna3483902
sumber

Bisakah Anda memberikan beberapa referensi untuk model RAM yang layak?

XL _At_Here_There

Lihat di atas di area, "... referensi ini menyatakan ..." memiliki tautan ke artikel.

user3483902

Terima kasih telah menunjukkan pekerjaan Brattka & Hertling, saya akan menyebutkannya saat itu saya lupa. Saya hanya ingin menunjukkan bahwa model RAM Layak tidak termasuk fungsi tingkat tinggi, khususnya tidak dapat menghitung batas urutan Cauchy (cepat), jadi saya tidak akan menghitungnya dengan menerapkan "real" dengan tepat. Dapat menghitung satu batas "di tingkat atas", jadi untuk berbicara (lihat bagian makalah di mana mereka berbicara tentang perkiraan fungsi rasional).

Andrej Bauer