النسخة الأصلية ل هذه القصة ظهرت في مجلة Quanta.
طرح سؤالاً على كرة سحرية 8 ، وسوف يجيب نعم ، لا ، أو شيء غير حاسم بشكل مزعج. نحن نفكر في الأمر كعب طفل ، لكن علماء الكمبيوتر النظريون يستخدمون أداة مماثلة. غالبًا ما يتخيلون أنهم يستطيعون استشارة الأجهزة الافتراضية التي تسمى Oracles والتي يمكن أن تجيب على الفور وصحيح على أسئلة محددة. ألهمت تجارب الفكر الخيالية هذه الخوارزميات الجديدة وساعدت الباحثين على تعيين مشهد الحساب.
يعمل الباحثون الذين يستشهدون أوراكليس في حقل فرعي لعلوم الكمبيوتر يسمى نظرية التعقيد الحسابي. إنهم مهتمون بالصعوبة المتأصلة في المشكلات مثل تحديد ما إذا كان الرقم هو أولي أو إيجاد أقصر مسار بين نقطتين في الشبكة. من السهل حل بعض المشكلات ، ويبدو أن البعض الآخر أكثر صعوبة ولكن لديه حلول يسهل التحقق منها ، في حين أن البعض الآخر سهل على أجهزة الكمبيوتر الكمومية ولكن يبدو أنه من الصعب على تلك العادية.
يريد منظري التعقيد فهم ما إذا كانت هذه الاختلافات الواضحة في الصعوبة أساسية. هل هناك شيء صعب جوهري حول بعض المشكلات ، أم أننا لسنا ذكيين بما يكفي للتوصل إلى حل جيد؟ يعالج الباحثون مثل هذه الأسئلة من خلال فرز المشكلات إلى “فصول التعقيد”-كل المشاكل السهلة في فصل واحد ، على سبيل المثال ، وتذهب جميع المشكلات السهلة للتحقق إلى أخرى-وإثبات نظريات حول العلاقات بين تلك الفئات.
لسوء الحظ ، تحولت رسم خرائط لمشهد الصعوبة الحسابية إلى أن تكون صعبة. لذلك في منتصف سبعينيات القرن العشرين ، بدأ بعض الباحثين في دراسة ما سيحدث إذا كانت قواعد الحساب مختلفة. هذا هو المكان الذي تأتي فيه أوراكليس.
مثل Magic 8 Balls ، Oracles هي أجهزة تجيب على الفور على الأسئلة نعم أو لا تكشف عن أي شيء عن أعمالهم الداخلية. على عكس كرات Magic 8 ، يقولون دائمًا إما نعم أو لا ، وهم دائمًا على صواب – ميزة كونها خيالية. بالإضافة إلى ذلك ، لن تجيب أي أوراكل معين فقط على نوع محدد من الأسئلة ، مثل “هل هذا الرقم الرئيسي؟”
ما الذي يجعل هذه الأجهزة الخيالية مفيدة لفهم العالم الحقيقي؟ باختصار ، يمكنهم الكشف عن اتصالات خفية بين فئات التعقيد المختلفة.
خذ فئتي التعقيد الأكثر شهرة. هناك فئة من المشكلات التي يسهل حلها ، والتي يسميها الباحثون “P” ، وفئة من المشكلات التي يسهل التحقق منها ، والتي يسميها الباحثون “NP”. هل كل مشاكل سهلة التحقق من السهل أيضًا حلها؟ إذا كان الأمر كذلك ، فهذا يعني أن NP سيساوي P ، وسيكون كل التشفير سهلاً (من بين عواقب أخرى). يشتبه منظري التعقيد في أن NP لا يساوي P ، لكنهم لا يستطيعون إثبات ذلك ، على الرغم من أنهم كانوا يحاولون تحديد العلاقة بين الفئتين لأكثر من 50 عامًا.
لقد ساعدتهم Oracles على فهم ما يعملون معه بشكل أفضل. اخترع الباحثون أوراكليس التي تجيب على الأسئلة التي تساعد في حل العديد من المشكلات المختلفة. في عالم حيث كان لكل جهاز كمبيوتر خط ساخن لأحد هذه الأوراق ، سيكون من السهل حل جميع المشكلات السهلة للتحقق ، وسوف تساوي P NP. لكن ORACLEs الأخرى الأقل فائدة لها تأثير معاكس. في عالم يسكنه هذه أوراكليس ، سيكون P و NP مختلفًا بشكل واضح.
