Bagaimana bilangan real ditentukan dalam perhitungan?

27

Ini mungkin pertanyaan dasar, tapi saya sudah membaca dan mencoba memahami makalah tentang mata pelajaran seperti perhitungan ekuilibrium Nash dan pengujian degenerasi linier dan tidak yakin bagaimana bilangan real ditentukan sebagai input. Misalnya, ketika dinyatakan bahwa LDT memiliki batas polinomial tertentu lebih rendah, bagaimana bilangan real ditentukan ketika mereka diperlakukan sebagai input?

cc.complexity-theory computability na.numerical-analysis computing-over-reals computable-analysis Philip White
sumber
1
Anda mungkin menemukan diskusi yang menarik di sini: en.wikipedia.org/wiki/Computable_number
Joseph Malkevitch
Seseorang harus menyatukan kertas-kertas ini dalam e-book gratis yang dapat diunduh.
Dilawar

Jawaban:

34

Saya tidak setuju dengan jawaban Anda yang diterima oleh Kaveh. Untuk pemrograman linier dan Nash equilibria, floating point mungkin dapat diterima. Tetapi angka floating point dan komputasi geometri bercampur sangat buruk: kesalahan pembulatan membatalkan asumsi kombinatorial dari algoritma, sering menyebabkan mereka crash. Lebih khusus, banyak algoritma geometri komputasi bergantung pada tes primitif yang memeriksa apakah nilai yang diberikan positif, negatif, atau nol. Jika nilai itu sangat dekat dengan nol dan pembulatan titik mengambang menyebabkannya memiliki tanda yang salah, hal-hal buruk dapat terjadi.

Sebaliknya, input sering diasumsikan memiliki koordinat bilangan bulat, dan hasil antara sering diwakili dengan tepat, baik sebagai bilangan rasional dengan presisi yang cukup tinggi untuk menghindari overflow atau sebagai bilangan aljabar. Perkiraan titik apung ke angka-angka ini dapat digunakan untuk mempercepat perhitungan, tetapi hanya dalam situasi di mana angka-angka dapat dijamin cukup jauh dari nol sehingga tes tanda akan memberikan jawaban yang tepat.

Dalam sebagian besar makalah algoritma teoritis dalam geometri komputasi, masalah ini dihindari dengan mengasumsikan bahwa input adalah bilangan real dan bahwa primitif adalah tes yang tepat dari tanda-tanda akar polinomial tingkat rendah dalam nilai input. Tetapi jika Anda menerapkan algoritma geometris maka ini semua menjadi sangat penting.

David Eppstein
sumber
Saya menyukai bagian dari jawaban Kaveh di mana ia menyarankan bahwa ada model komputasi alternatif, karena ini sepertinya sejalan dengan apa yang saya baca di koran yang saya lihat. Yang mengatakan, saya tidak benar-benar tahu jawabannya ... Saya belum menerima jawaban Kaveh untuk saat ini. Saya sebenarnya curiga bahwa angka aljabar mungkin ada hubungannya dengan itu. Bagaimanapun, terima kasih telah meluangkan waktu untuk mempertimbangkan pertanyaan saya ... Saya akan berpikir dan membaca lebih lanjut sebelum saya menerima jawaban.
Philip White
Saya belum mengatakan bahwa ini adalah model yang baik untuk CG, maksud saya adalah bahwa bahkan ketika penulis mengatakan input adalah bilangan real, mereka bukan bilangan real . Saya setuju dengan Anda bahwa saya seharusnya tidak memasukkan CG di antara yang lain. Saya telah membaca sangat sedikit makalah CG, apakah model BSS yang mapan dalam makalah CG teoretis?
Kaveh
1
Maafkan ketidaktahuan saya, tapi apa BSS berdiri untuk?
Philip White
1
Model BSS adalah model teoritis yang mengasumsikan bahwa bilangan real arbitrer tersedia. Apa yang dilakukan dalam CG melibatkan implementasi aktual dari model yang umumnya terbatas pada angka aljabar. Implementasi CG juga jauh dari biaya satuan per operasi. Jadi mereka bukan hal yang sama. Lihat misalnya model bilangan real LEDA, citeseerx.ist.psu.edu/viewdoc/…
David Eppstein
10
@ Kaveh: Tidak. Algoritme geometris dirancang untuk menjadi benar, dalam model RAM nyata, untuk input nyata sewenang-wenang, bukan hanya untuk input rasional. Secara khusus, ada algoritma geometris yang tidak dapat diimplementasikan dengan tepat, karena mereka menggunakan primitif yang sepele pada RAM nyata tetapi tidak ada algoritma yang efisien dikenal untuk RAM integer (realistis). Contoh terbaik adalah jumlah dari akar kuadrat masalah: Diberikan dua set dan bilangan bulat positif, adalah ? T ∑ s ∈ S √ST∑s∈Ss>∑t∈Tt
Jeffε
15

Anda juga dapat melihat ceramah Andrej Bauer tentang Peran Domain Interval dalam Aritmatika Nyata Exact Modern , yang mensurvei beberapa pendekatan berbeda untuk menentukan perhitungan atas bilangan real baik dalam teori maupun praktik.

Noam Zeilberger
sumber
8

Ini bukan jawaban langsung untuk pertanyaan Anda, lebih merupakan respons terhadap Raphael . Ada beberapa pekerjaan baru-baru ini menentukan perhitungan bilangan real menggunakan coinduction. Berikut adalah beberapa artikel tentang topik ini.

Mereka hampir tidak mencakup spektrum penuh perhitungan bilangan real, tetapi kemajuan sedang dibuat untuk mengatasi berbagai masalah.

Dave Clarke
sumber
1
Ide bagus tetapi karena Anda hanya dapat memiliki banyak definisi koinduktif, pendekatan ini tidak dapat mencakup seluruh . Apakah saya mengabaikan sesuatu? Atau apakah saya salah paham dan tujuannya adalah untuk mewakili paling tidak beberapa angka tepatnya? R
Raphael
Poin bagus. Saya tidak yakin apa keterbatasan dari pendekatan koinduktif. Pendekatan ini masih dalam tahap awal.
Dave Clarke
7

Kompleksitas komputasi perhitungan atas bilangan real dipertimbangkan oleh Blum, Cucker, Shub, dan Smale . Berikut ini sebagian deskripsi buku:

Teori komputasi klasik berawal pada karya Goedel, Turing, Gereja, dan Kleene dan telah menjadi kerangka kerja yang sangat sukses untuk ilmu komputer teoretis. Tesis buku ini, bagaimanapun, adalah bahwa ia menyediakan dasar yang tidak memadai untuk perhitungan ilmiah modern di mana sebagian besar algoritma adalah algoritma bilangan real. Tujuan buku ini adalah untuk mengembangkan teori komputasi formal yang mengintegrasikan tema-tema utama teori klasik dan yang lebih langsung berlaku untuk masalah-masalah dalam matematika, analisis numerik, dan komputasi ilmiah. Sepanjang jalan, penulis mempertimbangkan masalah mendasar seperti: Apakah Mandelbrot ditetapkan dapat dipilih? Untuk peta kuadratik sederhana, apakah Julia merupakan perangkat penghenti? Apa kompleksitas sebenarnya dari Newton? metode? Apakah ada algoritma untuk memutuskan masalah knapsack dalam sejumlah langkah ploynomial? Apakah Hilbert Nullstellensatz tidak bisa ditembus? Apakah masalah menemukan nol nyata dari gelar empat polinomial tidak dapat dipecahkan? Apakah pemrograman linier dapat ditelusuri lebih dari real?

Anda dapat menemukan ulasan buku ini di ACM SIGACT News .

MS Dousti
sumber
Buku ini terlihat sangat menarik, terima kasih.
Philip White
Anda dipersilahkan.
MS Dousti
5
Perlu dicatat bahwa model perhitungan BSS atas real adalah kontroversial, untuk alasan seperti apa yang David Eppstein sebut dalam komentar di atas. Sebagai contoh: aksioma BSS yang menghitung apakah x <y membutuhkan satu langkah waktu, untuk hasil acak x dan y. Sebaliknya, pendekatan seperti Type Two Effectivity (TTE) mendefinisikan mesin yang mengambil sebagai input input ke real, dan output mendekati computable untuk fungsi di atas real. Semakin banyak waktu berlalu, semakin baik pendekatan input dan output. Pendekatan itu terasa lebih realistis bagi saya.
Aaron Sterling
@ Harun Sterling: apakah Anda tahu referensi yang baik untuk Efektivitas Tipe Dua?
Joshua Grochow
3
@ Joshua Grochow: Maaf saya tidak sampai di sini lebih cepat. Buku yang dihubungkan Kaveh adalah "Nielsen dan Chuang" dari TTE. Namun, ini sangat sarat notasi sehingga akan tampak misterius bagi pembaca biasa. Sebagai gantinya, saya menyarankan slide tutorial Vasco Brattka berikut ini: cca-net.de/vasco/cca/tutorial.pdf
Aaron Sterling
7

Diedit / diperbaiki berdasarkan komentar

Ketika penulis berbicara tentang input bilangan real dalam pemrograman linier, perhitungan kesetimbangan Nash, ... di sebagian besar makalah (makalah yang tidak membahas topik komputasi / kompleksitas bilangan real), mereka tidak benar-benar berarti bilangan real. Mereka adalah bilangan rasional dan bilangan yang muncul dari mereka karena manipulasi mereka (bilangan aljabar). Jadi Anda bisa menganggapnya sebagai yang diwakili oleh string yang terbatas.

Di sisi lain, jika makalah ini berkomputasi dan kompleksitas dalam analisis , maka mereka tidak menggunakan model perhitungan yang biasa, dan ada berbagai model perhitungan / kompleksitas yang tidak sesuai dengan bilangan real.

Jika makalah tidak menentukan model perhitungan di atas bilangan real, Anda dapat dengan aman mengasumsikan bahwa ini adalah kasus pertama, yaitu hanya bilangan rasional.

Geometri komputasi berbeda. Dalam sebagian besar makalah di CG, jika penulis tidak menentukan model apa yang berkaitan dengan kebenaran dan kompleksitas algoritma yang sedang dibahas, dapat diasumsikan sebagai model BSS (alias real-RAM).

Model ini tidak realistis dan oleh karena itu implementasinya tidak langsung. (Ini adalah salah satu alasan bahwa beberapa orang di CCA lebih suka model teori Ko-Friedman / TTE / Domain , tetapi masalah dengan model ini adalah bahwa mereka tidak secepat perhitungan floating-point dalam praktek.) Kebenaran dan kompleksitas dari Algoritme dalam model BSS tidak perlu mentransfer ke kebenaran dari algoritma yang diterapkan.

Weihrauch ini buku berisi perbandingan antara model yang berbeda (Bagian 9.8). Hanya tiga halaman dan layak dibaca.

(Ada juga cara ketiga, yang mungkin lebih cocok untuk CG, Anda mungkin ingin melihat makalah ini:

Chee Yap, " Teori Komputasi Nyata menurut EGC "

di mana EGC adalah Persis Perhitungan Geometris .)

Kaveh
sumber
Saya pikir makalah saya terutama tertarik menentukan model, mengingat bahwa itu termasuk kalimat, "Kami sekarang secara resmi mendefinisikan model perhitungan kami." Makalah ini disebut "Batas Bawah untuk Masalah Kepuasan," dan tampaknya ada beberapa diskusi tentang pohon keputusan linear dan kueri polinomial. Jadi, saya pikir itulah jawaban yang saya cari di sana ... terima kasih. Saya akan membaca ulang koran dan melihat apakah saya bisa memahaminya.
Philip White
2
Saya tidak setuju. Ini adalah model yang salah untuk geometri komputasi. Lihat jawaban saya yang lebih terperinci di bawah ini.
David Eppstein
1
@ Kaveh: Saya pikir Anda harus mengatakan bahwa itu adalah angka rasional , bukan angka floating-point. Bilangan rasional yang tepat mudah diwakili oleh string berhingga, dan dalam banyak aplikasi (misalnya yang terkait dengan pemrograman linier) hasil antara juga akan menjadi bilangan rasional jika input Anda adalah bilangan rasional. (Tentu saja, seperti yang ditunjukkan David Eppstein, komp. Geom. Adalah pengecualian penting dalam arti bahwa hasil antara biasanya tidak rasional.)
Jukka Suomela
@ Jukka: Anda benar, saya akan mengganti floating-point dengan rasional.
Kaveh
5
Nggak. Ketika saya menulis "bilangan real", aku benar-benar berarti "bilangan real", dan maksud saya benar-benar bilangan real, benar-benar dari real. Sangat. Secara khusus, dalam makalah @Philip berbicara tentang, saya harus mengasumsikan algoritma bekerja untuk input nyata yang sewenang - wenang , sehingga saya dapat menerapkan hasil dari analisis non-standar.
Jeffε
3

Mereka tidak dan mereka tidak bisa, secara umum. Kami hanya dapat memperlakukan sejumlah input (dan output dan fungsi) yang dapat dihitung dengan model perhitungan kami. Khususnya, setiap input harus terbatas tetapi tidak semua bilangan real memiliki representasi terbatas.

Anda bisa, saya kira, mengasumsikan semacam oracle yang menghasilkan digit berikutnya dari nomor nyata tertentu berdasarkan permintaan (sth like a stream). Kalau tidak, Anda harus hidup dengan perkiraan (sewenang-wenang tepat).

Raphael
sumber
Jika ini benar maka bagaimana LDT dapat menangani angka nyata? Saya membaca sesuatu tentang "r-Linear Decision Trees" tetapi tidak benar-benar mengerti apa yang mereka bicarakan di koran, "Lower Bounds untuk masalah satsifiability linear."
Philip White
Saya yakin mereka tidak bisa atau mereka tidak menggunakan mesin Turing (atau conecpts yang setara). Jawaban lain yang tidak seketat / umum seperti milik saya harus menjelaskan hal ini.
Raphael