📽️ 👩🏿‍🤝‍👩🏽 ☯️ MIP * = RE: أدلة حديثة العهد في مجال علوم الكمبيوتر تسببت في تأثير الدومينو في الفيزياء والرياضيات 💡 👨🏻‍🍳 🚶🏿

وصل علماء الكمبيوتر إلى آفاق جديدة في التحقق من حلول للمشكلات بالطرق الحسابية. في نفس الوقت ، وجدوا إجابات على أهم الأسئلة المفتوحة لميكانيكا الكم والرياضيات البحتة.

في عام 1935 ، قام ألبرت أينشتاين ، بالتعاون مع بوريس بودولسكي وناثان روزين ، بالتحقيق في الإمكانية التي فتحتها القوانين الجديدة لفيزياء الكم: يمكن أن يكون جسيمان في حالة متشابكة عندما لا تنتهك المسافات الضخمة الاتصال البيني بينهما. في العام التالي ، صاغ آلان تورينج أول نظرية عامة للحساب ، وأثبت أن هناك مشاكل لا يمكن حلها بواسطة أجهزة الكمبيوتر. أحدثت هاتان الفكرتان ثورة في مجالات العلوم التي تتعلقان بها. بالإضافة إلى ذلك ، يبدو أنه ليس لديهم علاقة ببعضهم البعض. ولكن الآن الدليل

MIP * = RE جمعت بينهما ، مما أدى إلى حل العديد من المشاكل في مجال علوم الكمبيوتر والفيزياء والرياضيات.

تقوم أجهزة الكمبيوتر الكمومية بإجراء العمليات الحسابية باستخدام البتات الكمومية المتشابكة ، بدلاً من الأصفار الكلاسيكية والأخرى. تشير الدلائل الجديدة إلى أن هذه الحواسيب ، نظريًا ، يمكن استخدامها لاختبار حلول لعدد كبير من المشاكل. كانت العلاقة بين التشابك الكمي والحوسبة التقليدية مفاجأة كبيرة للعديد من الباحثين.

ميغيل نافاسكويس طالب فيزياء الكم في معهد البصريات الكمومية والمعلومات الكمية في فيينا. وقال معلقاً على الأدلة "كانت تلك مفاجأة كاملة".

حدد المؤلفون المشاركون في الأدلة الهدف المتمثل في تحديد حدود النهج للتحقق من حلول المشاكل الحسابية. ينطوي هذا النهج على تشابك الكم. بعد اكتشاف هذه الحدود ، توصل الباحثون إلى حل مشكلتين أخريين ، والتي كانت تقريبًا نتيجة ثانوية لعملهم. نحن نتحدث عن فرضية Zirelson في الفيزياء فيما يتعلق بالنمذجة الرياضية للتشابك الكمومي والمشكلة ذات الصلة في الرياضيات البحتة - مشكلة Conn في نظرية فون Neumann الجبر (مشكلة تضمين Conn).

ونتيجة لذلك ، تسببت نتائج تطبيق الأدلة في الرياضيات والفيزياء في حدوث شيء مثل تأثير الدومينو.

"كل الأفكار تنتمي إلى نفس الفترة. يقول هنري يوين : "من الجيد رؤيتهم يجتمعون مرة أخرى بطريقة مذهلة") من جامعة تورنتو - أحد مؤلفي الأدلة المشاركين. إلى جانبه ، شارك في هذا العمل Chzhenfen Ji ( Zhengfeng of Ji ) من جامعة سيدني للتكنولوجيا ، وجون رايت ( جون رايت ) من جامعة تكساس في أوستن ، وأناند ناتاراجان ( أناند ناتاراجان ) وتوماس فيديتش ( بواسطة توماس فيديك ) من معهد كاليفورنيا للتكنولوجيا. يعمل جميع العلماء الخمسة في مجال علوم الكمبيوتر.

مشاكل غير قابلة للذوبان

لقد وضع تورنج ، حتى قبل ظهور أجهزة الكمبيوتر ، الأساس الذي تقوم عليه التأملات في الحوسبة. وفي الوقت نفسه ، أظهر أن هناك مشكلة معينة ، وهي ثابتة ، لا يمكن للحواسيب حلها. هذه هي مشكلة الإغلاق.

عادة ، تتلقى برامج الكمبيوتر شيئًا ما عند الإدخال وتولد المخرجات. لكن في بعض الأحيان يعلقون في دورات لا نهاية لها ، مما يعني أنهم لا يتوقفون أبدًا. عندما يحدث هذا ، هناك طريقة واحدة للخروج من هذا الوضع. وفقًا لهنري يوين ، تحتاج إلى إيقاف البرنامج يدويًا. تحتاج فقط إلى وضع حد لعملها.

أثبت تورينج أنه لا توجد خوارزمية عالمية قادرة على معرفة ما إذا كان البرنامج سيتم إيقافه. من أجل معرفة ذلك ، تحتاج إلى تشغيل البرنامج.

هنري يوين ، توماس ويدك ، زينجفينج جي ، أناند ناتاراجان ، جون رايت

"لقد انتظرت مليون سنة ، ولم يتوقف البرنامج. ربما عليك فقط الانتظار مليوني سنة؟ يقول وليام سلوفسترا ( ويليام سلوفسترا ) ، عالم الرياضيات من جامعة واترلو: "لا توجد طريقة لإخبارها مسبقًا".

أثبت تورينج ، من وجهة نظر فنية ، أن مشكلة الإغلاق غير قابلة للحل. حتى أقوى كمبيوتر يمكنك تخيله غير قادر على التعامل معه.

بعد تورنج ، بدأ علماء الكمبيوتر بتصنيف المهام الأخرى حسب تعقيدها. تتطلب المهام الأكثر تعقيدًا المزيد من طاقة المعالجة - مزيد من وقت المعالج والذاكرة. هذه دراسة التعقيد الحسابي للخوارزميات.

ونتيجة لذلك ، تطرح أي مشكلة سؤالين كبيرين للباحثين: "ما مدى صعوبة حلها؟ ما هي صعوبة التحقق من صحة الحل الناتج؟ "

استجواب القرار من خلال الاستجواب

إذا كانت المهام بسيطة نسبيًا - يمكن التحقق من حلولها بشكل مستقل. ولكن عندما تصبح المهام أكثر تعقيدًا ، قد يكون التحقق من نتائج حلها أمرًا صعبًا للغاية. على الرغم من ذلك ، في عام 1985 ، قرر علماء الكمبيوتر أنه من الممكن بناء الثقة في صحة الإجابة حتى لو لم يكن من الممكن تأكيد ذلك بأنفسهم.

تتبع طريقة التحقق منطق استجواب الشرطة.

إذا روى المشتبه به قصة مدروسة بعناية ، فلن يتمكن المحقق من أخذ كل تفاصيلها والعثور عليها بالتأكيد. ولكن من خلال طرح الأسئلة الصحيحة ، يمكنك إما الإمساك بالمشتبه به عند الكذب ، أو تأكيد صحة قصته.

فيما يتعلق بعلوم الكمبيوتر ، فإن وجهي الاستجواب يمثلهما جهازي كمبيوتر. الأول هو نظام حوسبة قوي يقدم حلاً للمشكلة. يدعى الشاهد. والثاني لم يعد مثل هذا الجهاز القوي الذي يطرح أسئلة المختبر لتحديد ما إذا كانت الإجابة التي يقدمها صحيحة. يسمى هذا الكمبيوتر المدقق.

فكر في مثال بسيط. افترض أن شخصًا (المدقق) يعاني من عمى الألوان. يدعي شخص آخر (الشاهد) أن الكرات مطلية بألوان مختلفة ولا تختلف عن بعضها البعض. لا يمكن للمحقق التحقق من هذا البيان نفسه. ولكن ، بعد أن بنى الاستجواب بذكاء ، يمكنه مع ذلك معرفة ما إذا كان الأمر كذلك حقًا.

للقيام بذلك ، يمكنك إخفاء الكرات خلف الظهر ومزجها. وبعد ذلك - اسأل المثل عن الكرة الموجودة في أي يد. إذا كانت مختلفة حقًا ، فيجب أن يجيب المثل دائمًا على هذا السؤال بشكل صحيح. ولكن إذا كان لديهم نفس اللون ، أي أنهم يبدون متشابهين تمامًا ، فإن نصف إجابات المثل ستصبح خاطئة.

يقول توماس Widick أنه إذا تبين أن أكثر من نصف إجابات مقدم العرض صحيحة ، فيمكن للمرء أن يكون واثقًا جدًا من أن الكرات لها ألوان مختلفة.

من خلال طرح أسئلة prover ، يمكنك التحقق من حلول فئة أكبر من المشاكل مما يمكنك التحقق من نفسك.

في عام 1988 ، قام علماء الكمبيوتر بفحص الموقف الذي يوجد فيه محرضان يقدمان حلولًا لنفس المشكلة. في النهاية ، إذا كان هناك اثنان من المشتبه بهم يمكن استجوابهم ، فإن هذا سيبسط الكشف عن الجريمة ، أو - التحقق من القرار ، حيث يمكن إجبارهم على اللعب ضد بعضهم البعض.

ووفقًا لتوماس ويدك ، فإن هذا يعطي المحقق تأثيرًا أكبر. يستجوب ويسأل أسئلة ذات صلة ويتحقق من الإجابات. إذا كان المشتبه بهم يقولون الحقيقة ، يجب أن تتطابق إجاباتهم مع بعضهم البعض معظم الوقت. إذا كذبوا ، غالبًا ما تتباعد إجاباتهم.

وبالمثل ، أظهر الباحثون أنه من خلال استجواب شاهدين بشكل منفصل ، وطرحهما أسئلة حول الحلول التي توصلوا إليها ، من الممكن التحقق بسرعة من حلول فئة أكثر شمولاً من المشاكل مما كانت عليه عندما يعملون مع أحد الأمثلة.

قد تبدو دراسات التعقيد الحسابي للخوارزميات نظرية بحتة ، لكنها ترتبط ارتباطًا وثيقًا بالعالم الحقيقي. الموارد التي تحتاجها أجهزة الكمبيوتر لحل المشكلات والتحقق من الحلول - الوقت والذاكرة - هي موارد مادية. لهذا السبب ، قد تغير الاكتشافات الجديدة في الفيزياء نهج دراسة التعقيد الحسابي.

يقول أناند ناتاراجان أنه إذا ابتعدنا عن القاعدة المادية الكلاسيكية للحسابات واخترنا شيئًا مختلفًا تمامًا ، مثل الآليات الكمومية ، فسوف نحصل أيضًا على نظرية جديدة للتعقيد الحسابي.

الدليل الجديد هو النتيجة النهائية لتصادم علماء الكمبيوتر في القرن الحادي والعشرين مع واحدة من أغرب أفكار الفيزياء في القرن الماضي - مع فكرة التشابك الكمي.

مشكلة كون

عندما يتشابك جسيمان ، في الواقع ، لا يؤثران على بعضهما البعض. لا توجد علاقة سببية بين أفعالهم. عمل أينشتاين ومؤلفوه المشاركون على هذه الفكرة في مقال عام 1935. بعد ذلك ، حاول الفيزيائيون وعلماء الرياضيات الوصول إلى طريقة رياضية لوصف ما يعنيه التشابك الكمي في الواقع.

ومع ذلك ، فقد أدت هذه الجهود إلى نتائج مختلطة. توصل العلماء إلى نموذجين رياضيين مختلفين للتورط. ومع ذلك ، لم يكن من الواضح ما إذا كانت هذه النماذج متكافئة مع بعضها البعض.

أدى وجود مثل هذا التنافر المحتمل ، بطريقة دائرية ، إلى ظهور مشكلة مهمة في مجال الرياضيات البحتة. هذه هي مشكلة كون في نظرية الجبر فون نيومان. في النهاية ، لعبت دور نوع من "الدليل" الذي استفاد منه خمسة من علماء الكمبيوتر في اشتقاق أدلةهم.

كانت الطريقة الأولى لنمذجة التشابك الكمي هي إدراك الجسيمات ككائنات معزولة مكانيًا عن بعضها البعض. لنفترض أن أحد هذه الجسيمات موجود على الأرض ، والآخر على المريخ. المسافة بينهما شيء يستبعد العلاقة السببية بينهما (يتم فصلهم سببيًا). هذا ما يسمى نموذج المنتج الموتر.

ولكن في بعض الحالات ، لا يكون الفصل السببي بين الكيانات واضحًا تمامًا. ونتيجة لذلك ، وصل علماء الرياضيات إلى طريقة ثانية أكثر عمومية لوصف الاستقلال السببي.

عندما لا يؤثر الترتيب الذي يتم فيه تنفيذ عمليتين على النتيجة ، تسمى العملية بالتبادل: 3x2 هي نفسها 2x3. في هذا النموذج الثاني ، تتشابك الجسيمات عندما تكون خصائصها مترابطة ، لكن الترتيب الذي يتم به إجراء القياسات لا يهم. يمكن للمرء أن يأخذ قياسات على الجسيمات A من أجل التنبؤ بزخم الجسيمات B ، والعكس بالعكس. في أي حال ، ستكون النتيجة هي نفسها. وهذا ما يسمى بنموذج التشابك مع عامل الإبدال.

يستخدم كل من وصف التشابك صفائف أرقام تسمى المصفوفات. تتكون المصفوفات من صفوف وأعمدة. يستخدم نموذج منتج الموتر المصفوفات بعدد محدود من الصفوف والأعمدة. يستخدم نموذج عامل التبديل كائنات أكثر عمومية تعمل كمصفوفات بعدد لا نهائي من الصفوف والأعمدة.

بمرور الوقت ، بدأ علماء الرياضيات في دراسة هذه المصفوفات كأشياء ذات اهتمام مستقل ، غير مرتبطة بأي شكل من الأشكال بالعالم المادي. تمشيا مع هذا العمل ، اقترح عالم الرياضيات آلان كونس في عام 1976 أنه يجب أن يكون من الممكن تقريب العديد من المصفوفات ذات البعد اللامتناهي باستخدام مصفوفات البعد المحدود. هذه إحدى عواقب مشكلة كون في نظرية الجبر فون نيومان.

في العقد التالي ، صاغ الفيزيائي بوريس تسيريلسون نسخة جديدة من هذه المشكلة ، والتي أعادتها مرة أخرى إلى مجال الفيزياء. اقترح Zirelson أن نماذج منتج الموتر وعامل التنقل متكافئة تقريبًا مع بعضها البعض. هذا البيان منطقي ، لأن كلا هذين النموذجين ، نظريًا ، طريقتان مختلفتان لوصف الظاهرة الفيزيائية نفسها. أظهر العمل اللاحق أنه بسبب العلاقة بين المصفوفات والنماذج المادية التي تستخدمها ، فإن مشاكل Conn و Zirelson مرتبطة بشكل غير مباشر: إذا تم حل أحدهما ، فسيتم حل الآخر.

لكن حل هاتين المشكلتين جاء من مكان غير متوقع تمامًا.

لعبة الفيزياء

في الستينيات ، توصل الفيزيائي جون بيل إلى اختبار لتحديد ما إذا كان التشابك الكمي ظاهرة فيزيائية حقيقية ، وليس مفهومًا نظريًا. استخدم الاختبار شيئًا يشبه اللعبة ، مما جعل نتائجه من الممكن معرفة ما إذا كانت آليات معينة لا تتعلق بالفيزياء العادية تعمل أثناء اللعبة.

في وقت لاحق ، أدرك علماء الكمبيوتر أن هذا الاختبار المتعلق بالتشابك الكمي يمكن استخدامه أيضًا كأداة للتحقق من الحلول للمشكلات المعقدة للغاية.

ولكن قبل المضي قدمًا ، لنتحدث عن اللعبة. تخيل أن هناك لاعبين: أليس وبوب ، وأيضًا ملعب 3 × 3. يعين مقدم العرض خطًا لـ Alice ويطالبها بإدخال 0 أو 1 في كل خلية ، بحيث يعطي مجموعها رقمًا فرديًا. يحصل بوب على عمود يجب ملؤه بالأصفار والأصفار حتى يعطي مجموعها رقمًا زوجيًا. سيفوزون إذا وضعوا نفس الرقم في المكان الذي يتقاطع فيه الصف والعمود. من المستحيل التواصل معه.

في الظروف العادية ، فإن أفضل ما يمكنهم فعله هو الفوز بنسبة 89٪ من الوقت. ولكن إذا أخذت في الاعتبار عامل التشابك الكمي ، فإن فرصهم تتحسن.

تخيل أن أليس وبوب قد تشابكا بين الجسيمات الكمومية. يأخذون قياسات جزيئاتهم ويستخدمون نتائج القياس للإشارة إلى ما يكتبون في كل خلية - 0 أو 1. نظرًا لأن الجسيمات متشابكة ، فإن نتائج القياس ستكون مرتبطة ببعضها البعض. وهذا يعني أيضًا أن إجراءات اللاعبين ستكون مترابطة. ونتيجة لذلك ، اتضح أنهم سيكونون قادرين على الفوز في المباراة دائمًا.

إذا كانت هناك أرقام مختلفة في الخلية حيث يتقاطع الصف والعمود ، فستفقد اللعبة. إذا كانا متساويين - وفاز.

لذلك ، إذا اتضح أن لاعبين حققوا نجاحًا مدهشًا في لعب هذه اللعبة ، فيمكننا أن نستنتج أنهم يستخدمون شيئًا مختلفًا عما يمكن أن تقدمه الفيزياء الكلاسيكية. تسمى تجارب "بيل" اليوم الألعاب "غير المحلية" ، في إشارة إلى فصل اللاعبين. في الواقع ، يقوم الفيزيائيون بإجراء ألعاب مماثلة في المختبرات.

يقول هنري يوين أنه على مر السنين ، أجرى العلماء تجارب لإثبات حقيقة هذه الظواهر المخيفة.

كما هو الحال مع تحليل أي لعبة ، قد تحتاج إلى معرفة عدد المرات التي يمكن للاعبين الفوز فيها في لعبة غير محلية ، نظرًا لأنهم يلعبون بأفضل ما يمكن. على سبيل المثال ، في حالة سوليتير ، يمكنك حساب تواتر الانتصارات المحتملة للشخص الذي يلعب بشكل مثالي.

ولكن في عام 2016 ، أثبت William Slofstra أنه لا توجد خوارزمية عامة لحساب أقصى احتمال للفوز في جميع الألعاب غير المحلية. ونتيجة لذلك ، سأل الباحثون السؤال: هل من الممكن حساب النسبة المئوية القصوى للمكاسب على الأقل تقريبًا ؟

توصل علماء الكمبيوتر إلى الإجابة باستخدام نموذجي التشابك الكمي الموصوف أعلاه. تحدد الخوارزمية التي تستخدم نموذج المنتج الموتر القيمة الدنيا للحساب التقريبي لأقصى احتمال للفوز في جميع الألعاب غير المحلية. تقوم خوارزمية أخرى تستخدم نموذج عامل التحويل بتعيين القيمة القصوى.

الجواب الذي تقدمه تطبيقات هذه الخوارزميات ، كلما كان أكثر دقة ، كلما طالت مدة البرنامج. إذا كانت فرضية Zirelson صحيحة ، وهذان النموذجان متكافئان ، فيجب أن يقترب الحدان الأدنى والأعلى من بعضهما البعض ، ويتحولان إلى قيمة واحدة تمثل أقصى احتمال تقريبي للفوز.

ولكن إذا كانت فرضية Zirelson غير صحيحة ، والنموذجان ليسا متكافئين ، فوفقًا لهنري يوين ، سيتم دائمًا فصل الحدود العليا والسفلى. ولن تكون هناك طريقة لحساب حتى النسبة المئوية التقريبية للمكاسب للألعاب غير المحلية.

استفاد خمسة باحثين في عملهم الجديد من الجدل حول ما إذا كان الحدان العلوي والسفلي يتقاربان ، وما إذا كانت فرضية Zirelson صحيحة أم خاطئة. لقد فعلوا ذلك من أجل العثور على إجابة للسؤال عن الحالات التي يمكن فيها التحقق من حلول المشاكل الحسابية.

مساعدة معقدة

في بداية عالمي الكمبيوتر الألفين ، بدأوا يتساءلون عن كيفية تغيير نطاق المهام ، والتي يمكن التحقق من حلولها من خلال "استجواب" اثنتين ممن يمتلكان جسيمات معقدة.

يعتقد معظم العلماء أن الارتباك يضر بالتحقق. في النهاية ، سيكون من الأسهل على "المشتبه بهما" التوفيق بين الشهادات الكاذبة إذا كان لديهما أي طريقة لتنسيق الردود.

ولكن على مدى السنوات القليلة القادمة ، أصبح من الواضح أن العبارة المعاكسة كانت صحيحة: من خلال "استجواب" المحققين الذين لديهم جسيمات معقدة ، يمكن التحقق من فئة أوسع بكثير من المشاكل من العمل مع المحققين الذين ليس لديهم مثل هذه الجسيمات.

يقول توماس ويدك إن التشابك هو طريقة لخلق الارتباطات التي يبدو أنها تساعد الشهود على الكذب. ولكن ، في الواقع ، يمكن استخدام هذه الظاهرة لمصلحتهم.

لفهم كيفية استخدامه ، تحتاج أولاً إلى التعامل مع النطاق شبه الطبيعي للمهام التي يمكن التحقق من حلولها بفضل هذا الإجراء التفاعلي.

تخيل رسمًا بيانيًا - مجموعة من النقاط (الذروات) متصلة بخطوط (وجوه). تحتاج إلى معرفة ما إذا كان من الممكن ، باستخدام ثلاثة ألوان ، طلاء القمم بحيث لا يوجد رأسان في الرسم البياني متصلان بالوجه وفي نفس الوقت يتم رسمهما بنفس اللون. إذا كان ذلك ممكنًا ، فإن مثل هذا الرسم البياني هو "ثلاثة ألوان".

إذا أعطيت زوجًا من الأدلة رسمًا بيانيًا كبيرًا جدًا ، وسوف يبلغان أنه "ثلاثة ألوان" ، فقد يتساءل المرء ما إذا كانت هناك طريقة للتحقق من إجابتها.

في حالة الرسوم البيانية الكبيرة جدًا ، سيكون من المستحيل التحقق من الإجابة مباشرة. بدلاً من ذلك ، يمكنك سؤال كل من المختبرين عن لون إحدى الذروتين المتصلين. إذا أبلغ كل منهم عن ألوان مختلفة ، وسوف يعطون إجابات متشابهة في كل مرة يسألون فيها ، فإننا على ثقة من أن الرسم البياني هو بالفعل "ثلاثة ألوان".

لكن حتى استراتيجية الاستجواب هذه لن تعمل على رسوم بيانية ضخمة ذات وجوه ورؤوس أكثر من ذرات الكون. حتى طرح سؤال محدد ("أخبرني بلون XYZ vertex") يصبح مشكلة لا تطاق لشخص يحاول التحقق من حل لمشكلة ما. كمية البيانات اللازمة لتحديد اسم قمة معينة أكبر من تلك التي يمكن للمدقق تخزينها في الذاكرة المتاحة لها.

لكن التشابك الكمي يجعل من الممكن مخطط العمل ، الذي يقوم الشهود أنفسهم في تطبيقه بصياغة الأسئلة.

"لا يحتاج المحقق إلى طرح الأسئلة. يقول جون رايت: "يجبر المحقق المؤيدين على صياغة هذه الأسئلة بشكل مستقل والإجابة عليها".

يحتاج المدقق إلى المحققين للإبلاغ عن ألوان القمم المتصلة. إذا كانت القمم غير متصلة ، فلن توضح إجابات الأسئلة أي شيء حول ما إذا كان الرسم البياني "ثلاثي الألوان" أم لا. بمعنى آخر ، يحتاج المحقق إلى مُختبرين لطرح الأسئلة ذات الصلة. يسأل أحد المفسرين عن الجزء العلوي من ABC ، والثاني عن الجزء العلوي من XYZ. من المفترض أن القمتين مرتبطتان ، على الرغم من حقيقة أنه لا أحد من البراهين يعرف أيهما "يفكر" الآخر. (وهذا مشابه لكيفية تأمل أليس وبوب بكتابة نفس الرقم في نفس الخلية ، على الرغم من حقيقة أنه لا أحد منهم يعرف أي صف أو عمود في الجدول يعمل مع الآخر.)

إذا قام اثنان من المحققين بصياغة هذه الأسئلة بشكل مستقل تمامًا ، فلن تكون هناك آلية لإجبارهم على اختيار الذروات المتصلة (المرتبطة) ، بحيث يتم ذلك بطريقة تسمح للمحقق بالتحقق من إجاباتهم. لكن مثل هذا الارتباط هو بالضبط ما يمكن أن يحققه التشابك الكمي.

يقول توماس ويدك إنهم سيستخدمون تعقيدات لإحالة جميع الحالات عمليا إلى الشهود. العلماء يجعلون المختبرين يختارون أسئلتهم.

في نهاية هذا الإجراء ، يبلغ كل من المحضرين عن لون قمة. يتحقق المدقق مما إذا كانت هذه ألوان مختلفة أم لا. إذا كان الرسم البياني بالفعل "ثلاثي الألوان" ، فيجب ألا يقوم المختبرون أبدًا بالإبلاغ عن نفس اللون.

وفقًا لهنري يوين ، إذا كان الرسم البياني "ثلاثي الألوان" ، فسيتمكن المختبرون من إقناع الباحث بأن الأمر كذلك بالفعل.

كما اتضح ، فإن إجراء التحقق هذا هو مثال آخر على لعبة غير محلية. الباحثات "يفوزون" إذا أقنعوا الباحث بأن قرارهم صحيح.

في عام 2012 ، توماس Widik و Tsuyoshi Ito) أثبت أنه يمكن للمرء أن يلعب مجموعة متنوعة من الألعاب غير المحلية باستخدام محققين معقدين لاختبار الحلول. ينطبق هذا ، على الأقل ، على نفس العدد من المهام التي يمكن التحقق منها عن طريق استجواب جهازي كمبيوتر كلاسيك. وبالتالي ، فإن استخدام الأدلة المربكة لا يضر بالتحقق. في العام الماضي ، أثبت أناند ناتاراجان وجون رايت أن التفاعل مع الشهود المعقدين يوسع بالفعل فئة المشاكل التي يمكن التحقق من حلولها.

لكن علماء الكمبيوتر لم يعرفوا النطاق الكامل للمهام التي يمكن التحقق من حلولها باستخدام هذا النهج. الآن يعرفون عن ذلك.

تأثير الدومينو

في عملهم الجديد ، أثبت خمسة علماء أن "استجواب" الشهود المرتبكين يجعل من الممكن التحقق من حلول المشاكل غير القابلة للحل ، بما في ذلك حل مشكلة الإغلاق.

يقول هنري يوين أن النماذج من هذا النوع لديها قدرات تحقق لا يمكن تصورها.

لكن مهمة التوقف غير قابلة للحل. وكانت هذه الحقيقة هي القوة الدافعة التي أدت إلى الدليل النهائي.

تخيل أنك سلمت البرنامج لزوجين من الشهود المرتبكين. سألتهم إذا كان هذا البرنامج سيتوقف. أنت على استعداد للتحقق من إجاباتهم من خلال نوع من الألعاب غير المحلية. يقوم المحللون بتوليد الأسئلة و "الفوز" بناءً على تنسيق إجاباتهم.

إذا توقف البرنامج بالفعل ، فيجب أن يكون المؤيدون قادرين على الفوز باللعبة في 100 ٪ من الحالات. هذا مشابه لمثال مع رسم بياني - إذا كان "ثلاثة ألوان" حقًا ، فيجب ألا يقوم المحققون المعقدون أبدًا بالإبلاغ عن نفس اللون للقمم المتصلة. إذا لم يتوقف البرنامج أبدًا ، فيجب ألا يفوز المختبرون إلا عن طريق الصدفة - في 50٪ من الحالات.

هذا يعني أنه إذا طلب منك شخص ما تحديد أقصى احتمال تقريبي للفوز بلعبة غير محلية معينة ، فسيتعين عليك أولاً حل مشكلة التوقف. لكن حل هذه المشكلة أمر مستحيل. هذا يعني أنه من المستحيل العثور على المستوى الأقصى التقريبي لاحتمال الفوز للألعاب غير المحلية وكذلك مشكلة التوقف.

وهذا بدوره يعني أن فرضية تسيريلسون خاطئة: نموذجا التشابك الكمي ليسا متكافئين. إذا كانت متساوية ، فسيكون من الممكن تقليل الحدود الدنيا والعليا إلى نفس القيمة وحساب أقصى احتمال تقريبي للفوز.

يقول David Pérez-García من جامعة كومبلوتنسي بمدريد أن مثل هذه الخوارزمية لا يمكن أن توجد ، ونتيجة لذلك يجب أن يكون النموذجان مختلفين.

يثبت العمل الجديد أن فئة المشاكل التي يمكن التحقق من حلولها بمساعدة أدوات تدقيق كمية معقدة ، وهي فئة تسمى MIP * ، تساوي تمامًا فئة المشكلات التي ليست أكثر تعقيدًا من مشكلة التوقف - فئة RE. يحتوي عنوان الورقة على إشارة موجزة لهذا: "MIP * = RE".

في سياق الدليل على أن فئتي التعقيد متساويان ، أثبت العلماء أن فرضية Tsirelson خاطئة ، والتي ، بفضل العمل السابق ، تعني أن فرضية Conn خاطئة أيضًا.

ذهل الباحثون العاملون في مجالات تخصصهم من حقيقة أنه تم الحصول على حلول لهذه المشاكل واسعة النطاق بفضل الأدلة من مجال علوم الكمبيوتر ، والتي ، على ما يبدو ، لا علاقة لها بالرياضيات والفيزياء.

يقول ميغيل نافازكيز أنه إذا رأى مقالًا بعنوان MIP * = RE ، لما كان يعتقد أن لديها شيئًا مشتركًا في عمله. كان مؤلفًا مشاركًا في عمل سابق يربط بين فرضيات Zirelson و Conn. بالنسبة له ، كانت هذه مفاجأة كاملة.

بدأ علماء الفيزياء والرياضيات الكموميون للتو بإتقان برهان جديد. قبل ذلك ، كان علماء الرياضيات مهتمين بمسألة ما إذا كان بإمكانهم تقريب مصفوفات البعد اللامتناهي ، باستخدام مصفوفات كبيرة ذات بعد محدود بدلاً من ذلك. الآن ، وبفضل حقيقة أن فرضية كون قد ثبت خطأها ، فإنهم يعرفون أنه لا يمكن القيام بذلك.

قال وليام سلوفسترا: "تشير نتائجهم إلى أن هذا غير ممكن".

لم يسع علماء الكمبيوتر إلى تحليل فرضية كون. ونتيجة لذلك ، ليسوا في أفضل وضع لشرح العواقب المحتملة لحل هذه المشكلة.

أنا شخصياً لست عالم رياضيات. يقول أناند ناتاراجان: "لا أفهم جيدًا الصيغة الأولية لفرضية كون".

يتوقع هو وشركاؤه المشاركون من علماء الرياضيات ترجمة النتائج الجديدة إلى لغتهم. كتب توماس ويدك في تقرير نشر عن الدليل: "ليس لدي أدنى شك في أنه لن تكون هناك حاجة في النهاية إلى نظرية التعقيد الحسابي للحصول على نتائج رياضية بحتة".

ومع ذلك ، عندما يتعرف الباحثون الآخرون على الدليل ، ينتهي طريق البحث ، الذي كان من الممكن الوصول إليه بفضله. لأكثر من ثلاثة عقود ، حاول علماء الكمبيوتر ببساطة معرفة المدى الذي يمكن أن تحققه الحلول التفاعلية للمشكلات. الآن أمامهم يكمن الجواب ، في شكل مقال طويل بعنوان بسيط وبصدى أفكار تورينج.

"هناك العديد من الأعمال التي يتساءل مؤلفوها فقط ما هي احتمالات إجراء التحقق باستخدام اثنتين من الأدلة المعقدة. الآن نحن نعرف مدى قوة هذا الإجراء. يقول أناند ناتاراجان: "لقد انتهت هذه القصة".

القراء الأعزاء! ماذا يعني الدليل MIP * = RE للمنطقة التي تعمل فيها؟