Key points are not available for this paper at this time.
تصف cw.w للأبعاد الظاهرة التي بموجبها (على الرغم من البحث المكثف والمستمر) لمشاكل البحث الهندسية المختلفة، لدينا فقط خوارزميات يكون أداؤها متزايدًا بشكل أسي في الأبعاد. النتائج الأخيرة هل يجب أن تعاني مشكلة بحث الجيران الأقرب الدقيقة من هذه اللعنة؟ نقدم بعض الأدلة لدعم هذه اللعنة. على وجه التحديد، نحقق في مشكلة بحث الجيران الأقرب الدقيقة والمشكلة ذات الصلة بالمطابقة الجزئية الدقيقة ضمن نموذج الاتصال غير المتناظر الذي استخدمه ميلترسن 36 لدراسة مشاكل هياكل البيانات. نستخرج حدودًا دنيا غير تافهة للمشكلة الدقيقة التي تقف في تناقض مع خوارزميات معروفة لبحث الجيران الأقرب التقريبي.
درس بورودين وآخرون (Sat,) هذا السؤال.