قام عالم رياضيات بحل مشكلة عمرها 30 عامًا على الحدود بين الرياضيات وعلوم الكمبيوتر. استخدم برهانًا مبتكرًا وأنيقًا يندهش زملاؤه من بساطته.
أثبت هاو هوانغ ، أستاذ الرياضيات المساعد في جامعة إيموري في أتلانتا ، فكرة رياضية تسمى تخمين الحساسية ، والتي ، بعبارات قاسية بشكل لا يصدق ، تدعي كم يمكنك تغيير الإدخال إلى وظيفة دون تغيير الناتج (هذا هي حساسيتها).
في العقود التي تلت اقتراح علماء الرياضيات لأول مرة حدسية الحساسية (دون إثباتها) ، أدرك علماء الكمبيوتر النظريون أن لها آثارًا ضخمة على تحديد أكثر الطرق فعالية لمعالجة المعلومات.
ما هو رائع في دليل هوانغ ، وفقًا لخبراء آخرين في هذا المجال ، ليس فقط أن هوانغ خلعه ، ولكن أيضًا الطريقة الأنيقة والمباشرة التي قام بها. لم يتم مراجعة برهانه رسميًا أو نشره في أي مجلة رياضيات. ولكن بعد وقت قصير من نشره هوانغ على الإنترنت في 1 يوليو ، سرعان ما قبله زملاؤه على أنه حقيقة.
كتب سكوت أرونسون ، عالم الكمبيوتر النظري بجامعة أوستن على مدونته ، "كلما كان هناك إعلان مثل هذا ، ~ 99٪ من الوقت إما أن الدليل خاطئ ، أو على أي حال يكون الأمر معقدًا جدًا على الغرباء لتقييمه" بسرعة. هذه واحدة من الحالات المتبقية وهي 1٪. أنا واثق من أن الدليل صحيح. لماذا؟ لأنني قرأته وفهمته. استغرق الأمر حوالي نصف ساعة. "
أشار رايان أودونيل ، أستاذ علوم الكمبيوتر الذي يدرس نظرية الأعداد في جامعة كارنيجي ميلون في بيتسبرغ ، إلى أن دليل هوانغ يمكن تلخيصه في تغريدة واحدة:
ما الذي أثبته هوانغ بالفعل؟
من أجل البساطة ، تخيل مكعبًا ثلاثي الأبعاد بجوانب يبلغ طول كل منها وحدة واحدة. إذا وضعت هذا المكعب في نظام إحداثيات ثلاثي الأبعاد (بمعنى أنه يحتوي على قياسات في ثلاثة اتجاهات) ، فسيكون هناك ركن واحد إحداثيات (0،0،0) ، قد يكون الزاوية المجاورة له (1،0،0) ، واحد فوقها قد يكون (0،1،0) وهكذا. يمكنك أن تأخذ نصف الزوايا (أربع زوايا) بدون وجود أي زوج من الجيران: (0،0،0) و (1،1،0) و (1،0،1) و (0،1،1) aren ' ر الجيران. يمكنك إظهار ذلك من خلال النظر إلى المكعب ، ولكننا نعرفه أيضًا لأنهم جميعًا مختلفون بأكثر من إحداثي.
قال عالم الرياضيات في الجامعة العبرية جيل كالاي إن تخمين الحساسية يتعلق بإيجاد عدد الجيران لديك عندما تأخذ أكثر من نصف زوايا مكعب ذي أبعاد أعلى ، أو مكعب مفرط. يمكنك كتابة إحداثيات المكعب الزائد كسلسلة من 1s و 0s ، حيث يكون عدد الأبعاد هو طول السلسلة ، قال Kalai لـ Live Science. على سبيل المثال ، بالنسبة إلى المكعب الزائد رباعي الأبعاد ، هناك 16 نقطة مختلفة ، مما يعني 16 سلسلة مختلفة من 1s و 0s تتكون من أربعة أرقام.
اختر الآن نصف زائد واحد من النقاط الفردية على المكعب الزائد (بالنسبة إلى المكعب الزائد رباعي الأبعاد ، وهذا يعني اختيار تسعة - أو 8 + 1 - نقاط مختلفة من إجمالي 16).
من هذه المجموعة الأصغر ، ابحث عن النقطة مع معظم الجيران - ما الأمر الحد الأدنى عدد الجيران يمكن أن يكون؟ (يختلف الجيران برقم واحد فقط. على سبيل المثال ، 1111 و 1110 جيران ، لأنك تحتاج فقط إلى تبديل رقم واحد لتحويل الرقم الأول إلى الثاني.)
أثبت هوانغ أن هذا الركن يجب أن يحتوي على عدد من الجيران على الأقل مثل الجذر التربيعي لعدد الأرقام - في هذه الحالة ، الجذر التربيعي لـ 4 - وهو 2.
بالنسبة للأبعاد المنخفضة ، يمكنك معرفة أن هذا صحيح بمجرد التحقق. ليس من الصعب التحقق من 16 إحداثيات على المكعب (أو "سلاسل") للجيران ، على سبيل المثال. ولكن في كل مرة تضيف بعدًا إلى المكعب ، يتضاعف عدد السلاسل. لذا يصعب التحقق من المشكلة بسرعة كبيرة.
مجموعة السلاسل التي يبلغ طولها 30 رقمًا - الإحداثيات إلى زوايا مكعب ثلاثي الأبعاد - تحتوي على أكثر من مليار سلسلة مختلفة ، مما يعني أن المكعب يحتوي على أكثر من مليار زوايا. مع سلاسل طولها 200 رقم ، يوجد أكثر من نوفميديليون. أي مليون مليار مليار مليار مليار أو 1 يليه 60 أصفار.
هذا هو السبب في أن علماء الرياضيات يحبون البراهين: يظهرون أن شيئًا ما صحيح في كل حالة ، وليس فقط الحالات السهلة.
"إذا ن يساوي مليون - وهذا يعني أن لدينا سلاسل بطول مليون - ثم التخمين هو أنك إذا أخذت 2 ^ 1،000،000-1 وأضفت 1 ، فهناك سلسلة بها 1000 جار - الجذر التربيعي لمليون ، قال قلائي.
قال Kalai إن آخر تقدم رئيسي في تخمين الحساسية جاء في عام 1988 ، عندما أثبت الباحثون أنه يجب أن تحتوي سلسلة واحدة على الأقل على لوغاريتم ن الجيران. هذا رقم أقل بكثير. لوغاريتم 1،000،000 هو 6 فقط. لذلك اكتشف دليل هوانغ للتو أن ما لا يقل عن 994 من الجيران الآخرين هناك.
دليل أنيق و "غامض"
قال كالاي عن دليل هوانغ "إنه أمر غامض للغاية". "إنها تستخدم" الأساليب الطيفية "، وهي طرق مهمة جدًا في العديد من مجالات الرياضيات. لكنها تستخدم الأساليب الطيفية بطريقة جديدة. لا يزال الأمر غامضًا ، ولكن أعتقد أنه يمكننا توقع أن هذه الطريقة الجديدة لاستخدام الأساليب الطيفية سيكون لها تدريجيًا المزيد من التطبيقات."
في الأساس ، تصور هوانغ المكعب الزائد باستخدام صفائف الأرقام في الصفوف والأعمدة (تسمى المصفوفات). وكتب ارونسون في مدونته أن هوانج اكتشف طريقة غير متوقعة تمامًا للتعامل مع مصفوفة بترتيب غير عادي من -1s و 1s "يجعل كل شيء يعمل بطريقة سحرية".
وقال كالاي إن هوانج "أخذ هذه المصفوفة ، وعدّلها بطريقة بارعة وغامضة للغاية". "يبدو أن لديك أوركسترا ويعزفون بعض الموسيقى ، ثم تدع بعض اللاعبين ، لا أعرف ، يقفون على رؤوسهم وتصبح الموسيقى مختلفة تمامًا - شيء من هذا القبيل."
وقال كالاي إن هذه الموسيقى المختلفة هي مفتاح إثبات التخمين. وقال إنه أمر غامض ، لأنه على الرغم من أن علماء الرياضيات يفهمون سبب نجاح الطريقة في هذه الحالة ، إلا أنهم لا يفهمون هذه "الموسيقى" الجديدة بالكامل أو في أي حالات أخرى قد تكون مفيدة أو مثيرة للاهتمام.
"لمدة 30 عامًا ، لم يكن هناك تقدم ، ثم حسم هاو هوانغ هذه المشكلة ، ووجد دليلاً بسيطًا جدًا على أن الإجابة هي الجذر التربيعي لـ نقال كالاي ، "لكن خلال هذه السنوات الثلاثين ... أدرك الناس أن هذا السؤال مهم جدًا في نظرية الحوسبة."
وقال كالاي إن إثبات هوانغ مثير لأنه يطور مجال علوم الكمبيوتر. لكنها جديرة بالملاحظة أيضًا لأنها قدمت طريقة جديدة ، ولا يزال علماء الرياضيات غير متأكدين من الطريقة الأخرى التي قد تسمح لهم طريقة هوانغ الجديدة بإنجازها.
