🤚🏽 🤤 👵🏾 يثبت البرهان الكبير على نظرية علم الحاسوب الفيزياء بالرياضيات 🐯 👖 👨🏽‍🚒

حدد المتخصصون في علوم الكمبيوتر آفاقًا جديدة في المعرفة التي تم التحقق منها من خلال الحساب. وفي نفس الوقت قاموا بحل مشاكل كبيرة من ميكانيكا الكم والرياضيات البحتة.

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

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

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

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

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

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

سقطت النتائج في نهاية المطاف مثل الدومينو.

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

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

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

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

"لا بد لي من تثبيت البرنامج يدويًا. قال إيوان.

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

Ewan و Vidik و Ji و Natarajan و Wright

“لقد انتظرت مليون سنة ، ولم ينته البرنامج من العمل. هل تحتاج إلى الانتظار مليون سنة أخرى؟ قال وليام سلوفسترا ، عالم الرياضيات في جامعة واترلو : "لا توجد إجابة على هذا السؤال" .

من الناحية الفنية ، فإن مهمة إيقاف البرنامج غير قابلة للحل - حتى أقوى جهاز كمبيوتر يمكنك تخيله لا يمكنه حله.

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

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

استجواب للتأكيد

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

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

من حيث المعلوماتية ، يحتوي الاستجواب على جهاز كمبيوتر قوي يقدم حلًا للمشكلة - يُعرف باسم "prover" - وجهاز كمبيوتر أقل قوة يطلب من prover من الأسئلة تحديد صحة الإجابة ، والمعروفة باسم "test".

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

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

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

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

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

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

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

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

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

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

فرضية تداخل كون

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

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

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

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

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

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

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

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

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

ومع ذلك ، فإن الحل لكلتا المشكلتين نتيجة لذلك ظهر في اتجاه مختلف تمامًا.

الفيزياء والألعاب

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

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

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

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

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

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

قال إيوان: "قام الناس بمثل هذه التجارب لسنوات ، ويترتب على ذلك أن هذا التأثير المخيف موجود بالفعل".

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

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

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

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

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

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

مساعدة معقدة

في أوائل العقد الأول من القرن الحادي والعشرين ، ظن علماء الكمبيوتر: كيف سيتغير نطاق المهام ، والتي يمكن تأكيد حلولها من خلال إجراء مقابلتين مع جسيمات معقدة؟

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

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

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

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

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

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

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

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

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

"لا يحتاج المراجع إلى معرفة الأسئلة. قال المفتش إن المفتشين يجعلون أنفسهم يحسبون الأسئلة له.

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

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

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

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

قال إيوان: "إذا كان العد يمكن رسمه بثلاثة ألوان ، فيمكن للباحثين إقناعك بذلك".

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

في عام 2012 ، أثبت Vidik و Tsiyoshi Ito أنه من الممكن ، من خلال لعب العديد من الألعاب غير المحلية بأدلة مربكة ، تأكيد الإجابات على نفس العدد من المهام على الأقل عند استجواب جهازي كمبيوتر كلاسيكيين. أي أن استخدام المحرضين المربكين لا يضر بتأكيد فتحاتهم. وفي العام الماضي ، أثبت Natarajan و Wright أن التفاعل مع المُثبِّتين المعقدين يوسع بالفعل فئة المهام التي تم التحقق من صحتها.

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

سلسلة من العواقب

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

قال إيوان: "إن قدرات التحقق من صحة هذا النموذج مذهلة".

ومع ذلك ، لا يمكن حل مشكلة التوقف. وأصبحت هذه الحقيقة أساسية لاستكمال الدليل.

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

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

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

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

قال ديفيد بيريز جارسيا من جامعة كومبلوتنسي بمدريد: "لا يمكن أن تكون هناك مثل هذه الخوارزمية ، لذا يجب أن يكون النموذجان مختلفين".

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

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

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

قال نافازكيز ، المؤلف المشارك في عمل سابق يربط بين فرضية Cirelson وفرضية Conn حول التعشيش: "عندما رأيت عملًا يسمى MIP * = RE ، لم أكن أعتقد بالتأكيد أن له أي علاقة بعملي". "لقد كانت مفاجأة لي."

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

قال سلوفسترا "من نتيجتهم ، هذا مستحيل".

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

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

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

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

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

يثبت البرهان الكبير على نظرية علم الحاسوب الفيزياء بالرياضيات