Dalam SODA 1995 , Jeff Erickson menunjukkan batas yang lebih rendah untuk kepuasan linear (memeriksa apakah beberapa subset dari bilangan real memenuhi persamaan linear pada variabel r ). Metode pembuktian menggunakan infinitesimal dan prinsip transfer Tarski .
Bisakah seseorang menjelaskan intuisi di balik rute yang diambil untuk membuktikan ikatan ini? Apa kesulitan dalam menghasilkan bukti langsung seperti ini: "Mengingat pohon keputusan yang mengambil bilangan real, inilah cara kita dapat membangun input permusuhan"?
Jawaban:
Saya sangat menyarankan untuk membaca makalah tindak lanjut yang lebih baru oleh Ailon dan Chazelle , yang menghindari keseluruhan masalah yang sangat kecil. Jika Anda ingin tetap dengan makalah saya, silakan baca versi jurnal ( Chicago J Theoretical Computer Science 1999 ). Versi SODA memiliki bug utama di Bagian 5, dan (saya pikir) versi jurnal menjelaskan bukti utama dengan lebih jelas.
sumber
Memang, argumen utama adalah untuk membangun pohon keputusan dan merancang input permusuhan, tetapi ada masalah teknis dengan melakukan hal ini yang sangat dihindari oleh infinitesimal. Lihatlah diskusi di bagian bawah halaman 2 kolom pertama, dan lanjutkan, yang menjelaskan hal ini dengan cukup jelas.
sumber