Batas bawah untuk masalah kepuasan linear

10

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 .rnr

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"?

Jagadish
sumber
1
Saya berasumsi Anda merujuk pada dokumen ini: portal.acm.org/citation.cfm?id=313772
MRA
1
diedit dengan tepat
Suresh Venkat
Ya, itulah makalah yang saya maksud. @suresh terima kasih
Jagadish

Jawaban:

2

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.

Suresh Venkat
sumber