50 عاما من رحلة نظرية التعقيد إلى حدود المعرفة | مجلة كوانتا

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

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

قال كارموسينو: "أنا 100٪ لم أفهم". "لكنني علمت أنني أريد ذلك."

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

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

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

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

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

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

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

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

معروف غير معروف

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

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

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

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

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

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

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

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

ثم في عام 1936 ، أعاد طالب دراسات عليا يبلغ من العمر 23 عامًا يُدعى آلان تورينج صياغة حالة قابلية التحديد لهيلبرت بلغة الحساب غير المألوفة آنذاك ووجهها لضربة قاتلة. صاغ تورينج نموذجًا رياضيًا - يُعرف الآن باسم آلة تورينج - يمكن أن يمثل ذلك جميع الخوارزميات الممكنة ، ويظهر أنه إذا كان إجراء هيلبرت موجودًا ، فسيكون مناسبًا لهذا النموذج. ثم استخدم أساليب مرجعية ذاتية مثل Gödel's to يثبت وجود عبارات غير قابلة للتقرير - أو ، على نحو مكافئ ، مشاكل غير قابلة للحساب لا يمكن لأي خوارزمية حلها.

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

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

قال كارموسينو: "ظهرت نظرية ثرية ، ولم نعد نعرف الإجابات".

مسارات متشعبة

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

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

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

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

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

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

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

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

صعب عالميًا

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

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

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

في نفس الوقت تقريبًا ، تم تسمية طالب دراسات عليا في الاتحاد السوفيتي ليونيد ليفين ثبت أ نتيجة مماثلة، باستثناء أنه حدد عدة مشاكل عالمية مختلفة. بالإضافة إلى ذلك ، المنظر الأمريكي التعقيد ريتشارد كارب ثبت أن خاصية العالمية التي حددها Cook (و Levin ، على الرغم من أن Karp و Cook لم يعرفوا بعمل ليفين إلا بعد سنوات) كانت في حد ذاتها عالمية. تقريبًا كل مشكلة NP بدون خوارزمية متعددة الحدود معروفة - أي تقريبًا كل مشكلة يمكن التحقق منها بسهولة والتي تبدو صعبة - لها نفس الخاصية ، والتي أصبحت تُعرف باسم NP-Complete.

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

ستكون تسوية صعوبة أي مشكلة كاملة NP كافية لحل سؤال P مقابل NP. إذا كانت P ≠ NP ، فإن التمييز بين المشكلات السهلة والمشكلات الصعبة يتم إيقافه بواسطة آلاف الأعمدة المتساوية في القوة. إذا كان P = NP ، فإن الصرح بأكمله يتأرجح على حافة الانهيار ، فقط في انتظار سقوط قطعة واحدة.

توحد كوك وليفين وكارب ما بدا وكأنه العديد من المشاكل غير ذات الصلة. الآن كل ما كان على منظري التعقيد فعله هو حل مشكلة واحدة: هل P = NP أم لا؟

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

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

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

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

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

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

قال كارموسينو: "لقد كان مثل ،" كما تعلم ، إذا كنت تريد الاستمرار في القيام بذلك ، إذا كنت تريد الاستمرار في ممارسة علوم الكمبيوتر النظرية ونظرية التعقيد ، فيمكنك: إنها تسمى مدرسة الدراسات العليا ". بعد حصوله على درجة الماجستير ، انتقل إلى سان دييغو في عام 2012 للعمل للحصول على درجة الدكتوراه التي يشرف عليها Impagliazzo.

كان الهدف الرئيسي لـ Carmosino ، في البداية ، هو فهم أفضل لـ ورقة تاريخية منذ عقدين من الزمان استحوذت على خياله. تلك الورقة ، من قبل أصحاب النظريات المعقدة الكسندر رازبوروف و ستيفن روديتش، أظهر أن استراتيجية "طبيعية" معينة لإثبات P ≠ NP ستفشل بشكل شبه مؤكد ، لأن النجاح سيأتي بتكلفة باهظة - الانهيار الكامل للتشفير - الذي اعتبره الباحثون أمرًا مستبعدًا للغاية. فسر الباحثون نتيجة Razborov و Rudich على أنها عائق أمام هذا النهج الشائع لإثبات P ≠ NP.

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

قال إيلانغو: "نظرية التعقيد ملعون ومباركة بالعديد من الحواجز".

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

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

مسار دائري

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

بدت شانون ، التي نشأت في بلدة صغيرة في شمال ميشيغان ، شخصية غير مرجحة لدخول عصر المعلومات. ومع ذلك فقد جسَّد الطبيعة متعددة التخصصات للتخصصات الناشئة في علوم الكمبيوتر ، حيث يشعر بنفس القدر في المنزل في الهندسة الكهربائية والمنطق الرياضي. في رسالة الماجستير، أظهر شانون كيف يمكن للدوائر المصنوعة من المفاتيح الكهروميكانيكية أن تمثل تعبيرات منطقية تتضمن متغيرات منطقية - وهي كميات يمكن أن تأخذ قيمتين فقط (مثل صواب أو خطأ ، أو 1 و 0).

في هذه التعبيرات ، ترتبط المتغيرات المنطقية ببعضها البعض بواسطة "البوابات المنطقية" AND و OR و NOT. التعبير الأولي A و B ، على سبيل المثال ، يكون صحيحًا عندما يكون كل من A و B صحيحين ، وخطأ في الحالات الأخرى ؛ من ناحية أخرى ، يكون A OR B صحيحًا إذا كان أحد المتغيرين على الأقل صحيحًا. بوابة NOT هي أبسط: فهي تعكس قيمة متغير واحد. باستخدام ما يكفي من هذه الكتل الأساسية ، يمكنك إجراء أي عملية حسابية على الإطلاق.

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

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

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

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

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

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

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

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

قال آرونسون: "ليس هناك ما يكفي من الدوائر الصغيرة للالتفاف".

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

كريبتو بروس

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

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

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

قال رازبوروف: "لقد كنت محظوظًا لأنني لم أكن أعرف مدى صعوبة هذه المشكلة". "لولا ذلك ربما لم أكن لأبدأ حتى."

قام Razborov بتحليل الدوائر التي تحتوي فقط على بوابات AND و OR ، و ثبت أن وظيفة معينة كان من الصعب حسابها باستخدام مثل هذه الدوائر ، بغض النظر عن كيفية ترتيب البوابات - والأكثر من ذلك ، أن هذه الوظيفة كانت معروفة بأنها NP-Complete. كان كل ما كان على الباحثين فعله لحل P مقابل NP هو توسيع تقنيات Razborov لتشمل الدوائر ذات البوابات NOT.

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

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

قال إمباجليازو: "نكتنا أننا سنحصل على زر يقول" مرجع ذاتي ".

كطلاب دراسات عليا ، عمل كل من Rudich و Impagliazzo على الأسس النظرية المعقدة للتشفير ، وهو موضوع ربما يقدم أفضل دافع عملي لمحاولة إثبات P ≠ NP. يخفي المشفرون الرسائل السرية بإخفائها في "العشوائية الزائفة" - ستبدو الرسالة المشفرة بهذه الطريقة وكأنها خليط عشوائي من الأرقام لأي متصنت ، ولكن لا يزال من الممكن فك تشفيرها من قبل المستلم المقصود. ولكن كيف يمكنك أن تتأكد من أن أي شخص متنصت سيجد صعوبة بالغة في كسر الشفرة؟

هذا هو المكان الذي تأتي فيه نظرية التعقيد. تعتمد طرق التشفير الأكثر استخدامًا اليوم على مشكلات NP التي تبدو صعبة - لفك تشفير الرسالة ، سيحتاج المهاجم إلى خوارزمية سريعة لم يتم اكتشافها بعد لحل المشكلة. لإثبات أن هذه الطرق آمنة حقًا ، هناك شيء واحد عليك القيام به هو إثبات أن P ≠ NP. قال Sipser إنه بدون دليل ، كل ما يمكنك فعله هو "الأمل في ألا يكون من تحاول إخفاء السر عنه عالم رياضيات أفضل منك."

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

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

نكتة قاسية

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

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

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

قال كارموسينو: "لا يمكنك إلا أن تحصل على أكثر مما كنت تتمناه".

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

لفهم هذا الاتصال ، تخيل النظر إلى عمود الإخراج في جدول الحقيقة للدالة المنطقية مع العديد من متغيرات الإدخال واستبدال كل "صحيح" بـ 1 وكل "خطأ" بـ 0:

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

لذلك أظهرت نتيجة Razborov و Rudich أن أي دليل طبيعي على P NP سوف ينتج أيضًا خوارزمية سريعة يمكن أن تميز السلاسل العشوائية الكاذبة التي تحتوي على رسائل مخفية من تلك العشوائية حقًا. سيكون التشفير الآمن أمرًا مستحيلًا - وهو عكس ما كان الباحثون يأملون في تأسيسه من خلال إثبات P ≠ NP.

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

قال كابانيتس: "إذا كنت تؤمن بالصلابة ، فعليك أن تؤمن أنه من الصعب إثبات الصلابة".

في ميتافيرس

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

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

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

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

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

سلطت ورقة Kabanets and Cai الضوء على مشكلة حسابية ضمنية في صياغة Razborov و Rudich لحاجز البراهين الطبيعية: بالنظر إلى جدول الحقيقة للدالة المنطقية ، حدد ما إذا كانت تحتوي على دائرة عالية أو منخفضة التعقيد. لقد أطلقوا على هذا اسم مشكلة الحد الأدنى لحجم الدائرة ، أو MCSP.

MCSP هي مشكلة تعقيد ميتا جوهرية: مشكلة حسابية موضوعها ليس نظرية الرسم البياني أو موضوع خارجي آخر ، ولكن نظرية التعقيد نفسها. في الواقع ، إنها تشبه النسخة الكمية للسؤال التي دفعت منظري التعقيد إلى التعامل مع P مقابل NP باستخدام نهج تعقيد الدوائر في الثمانينيات: ما هي الوظائف المنطقية التي يصعب حسابها ، وأيها سهلة؟

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

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

بالنسبة للمشكلات في NP ، "ما مدى صعوبة ذلك؟" عادة ما تكون الإجابة سهلة بما يكفي ، ولكن يبدو أن MCSP غريب. قال كابانيتس: "لدينا عدد قليل جدًا من المشاكل" العائمة "التي لم يتم ربطها بهذه الجزيرة من مشاكل NP الكاملة ، على الرغم من أنها تبدو صعبة".

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

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

"إنه ، بمعنى ما ، تعقيد ميتا ،" قال راهول سانتانام، منظّر التعقيد في جامعة أكسفورد.

ولكن هل كانت الصلابة على طول الطريق ، أو كانت هناك على الأقل طريقة ما لفهم سبب عدم نجاح الباحثين في إثبات أن MCSP مكتمل NP؟ اكتشف Kabanets أنه ، نعم ، كان هناك سبب: تعمل صعوبة فهم تعقيد الدائرة كحاجز أمام أي استراتيجية معروفة لإثبات اكتمال NP لـ MCSP - وهي مشكلة تتعلق بصعوبة فهم تعقيد الدائرة. بدا منطق حاجز البراهين الطبيعية الملتوي والذاتي الهزيمة لا مفر منه.

من المحتمل أيضًا أن MCSP ليس مكتمل NP ، ولكن هذا أيضًا يبدو غير مرجح - بعض المتغيرات الأبسط للمشكلة معروفة بالفعل بأنها مكتملة NP.

قال إمباجليازو: "ليس لدينا مكانًا لطيفًا لوضعه على أنه يرتبط ارتباطًا مباشرًا بجميع المشكلات الأخرى التي ندرسها".

لقد ألقى Kabanets الضوء على السلوك الغريب لـ MCSP ، لكنه لم يكن يعرف كيف يحرز مزيدًا من التقدم. تباطأت أبحاث ما وراء التعقيد إلى حدٍ كبير. ستزدهر مرة أخرى بعد 16 عامًا ، عندما اكتشف الباحثون علاقة مفاجئة بسؤال أساسي آخر: ما مدى صعوبة حل المشكلات إذا كنت مهتمًا فقط بالحصول على الإجابة الصحيحة في معظم الأوقات؟

حرب العوالم

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

قال كارموسينو: "كنت مهووسًا بتلك الورقة في ذلك الوقت". "لم يتغير شيء."

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

يتذكر كابانيتس قائلاً: "لقد كان يتنصت على الناس بطريقة جيدة".

في البداية ، كان لدى Carmosino أفكار جديدة لإثبات اكتمال NP لنسخة MCSP التي ظهرت في ورقة Razborov و Rudich حول حاجز البراهين الطبيعية. لكن هذه الأفكار لم تنجح. بدلاً من ذلك ، جعلت ملاحظة غير تقليدية من قبل Impagliazzo الباحثين الأربعة يدركون أن حاجز البراهين الطبيعية يمكن أن ينتج خوارزميات أكثر قوة مما أدركه أي شخص - كانت هناك خريطة سرية محفورة في الحاجز.

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

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

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

ولكن بالنسبة لبعض الإصدارات الأبسط من MCSP - التي تميز جداول الحقيقة عالية التعقيد عن تلك منخفضة التعقيد عندما تكون هناك قيود محددة على الدوائر - كانت الخوارزميات السريعة معروفة لسنوات عديدة. أظهرت ورقة Carmosino و Impagliazzo و Kabanets و Kolokolova أنه يمكن تحويل هذه الخوارزميات إلى خوارزميات تعليمية كانت مقيدة بالمثل ولكنها لا تزال أقوى من أي خوارزميات سبق أن فهمها الباحثون على هذا المستوى النظري الدقيق.

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

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

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

قال إمباجليازو: "هذا النوع من الازدواجية هو موضوع طيلة ما لا يقل عن 30 أو 40 عامًا من التعقيد". "غالبًا ما تكون العقبات هي الفرص".

الائتمان الجزئي

تسارع التقدم في السنوات التي تلت نشر كارموسينو وزملاؤه ورقتهم البحثية.

قالت كولوكولوفا: "تحدث أشياء جديدة". "هناك الكثير من الباحثين المبتدئين ، حقا ، حقا."

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

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

باحث شاب آخر مستوحى من Allender هو شويتشي هيراهارا، الآن أستاذ في المعهد الوطني للمعلوماتية في طوكيو. بينما كان لا يزال طالب دراسات عليا في عام 2018 ، كشف Hirahara المدى الحقيقي للعلاقة بين التعقيد الفوقي وتعقيد الحالة المتوسطة الذي اكتشفه كارموسينو وزملاؤه. وجد هؤلاء الباحثون الأربعة علاقة بين متوسط ​​تعقيد مشكلة واحدة - MCSP - وأسوأ حالة تعقيد لمشكلة أخرى - التعلم المنطقي. طور Hirahara تقنياتهم إلى أبعد من ذلك استخلاص تخفيض من الأسوأ إلى متوسط ​​الحالة لـ MCSP. تشير نتيجته إلى أن خوارزمية MCSP افتراضية متوسطة الحالة مثل تلك التي اعتبرها كارموسينو وزملاؤه ستكون قوية بما يكفي لحل نسخة مختلفة قليلاً من MCSP دون ارتكاب أي أخطاء.

كانت نتيجة Hirahara مثيرة لأن العديد من الباحثين يشكون في أن MCSP مكتمل NP ، على عكس جميع المشكلات الأخرى التي يُعرف عنها انخفاض الحالة الأسوأ إلى الحالة المتوسطة. إذا تمكنوا من توسيع نتائج Hirahara لتغطية جميع خوارزميات الحالة المتوسطة ثم إثبات أن MCSP مكتمل NP ، فسيثبت ذلك أننا لا نعيش في Heuristica.

قال سانتانام: "ستكون هذه نتيجة مذهلة حقًا".

قد يبدو إثبات أن MCSP مكتمل NP أمرًا صعبًا - بعد كل شيء ، كان السؤال مفتوحًا لأكثر من 50 عامًا. ولكن بعد أ اختراق في العام الماضي بواسطة Hirahara ، أصبح الباحثون الآن أقرب بكثير مما كان يتوقعه أي شخص قبل بضع سنوات.

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

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

حفزت هذه النتيجة الباحثين في مجال التعقيد الفوقي أكثر حتى من عمل Hirahara السابق ، وقد لاحظ باحثون آخرون أيضًا - أطلق عليها مُنظِّر التعقيد والمدون Lance Fortnow اسم نتيجة العام. ذلك لأن معالجة إصدارات "الوظيفة الجزئية" من المشكلات الحسابية كان خطوة وسيطة رئيسية في براهين اكتمال NP الأخرى.

قال ويليامز: "إنه عمل رائع". "اعتقد الجميع أن هذه المشاكل الجزئية كانت تقريبًا نفس صعوبة المشكلة الكاملة."

لا تزال هناك عوائق أمام إثبات اكتمال NP للنسخة الكاملة من MCSP. ولكن ليس هناك نوع من الحواجز التي تشير إلى أن هناك حاجة إلى مجموعة أدوات جديدة تمامًا - قد يكون الأمر مجرد مسألة إيجاد الطريقة الصحيحة للجمع بين التقنيات المعروفة. من شأن الدليل أن يحسم أخيرًا حالة إحدى المشكلات القليلة التي قاومت التصنيف طالما كانت نظرية التعقيد موجودة. عبر البريد الإلكتروني ، كتب ليفين: "من شأنه أن يتواضع لي أن أظهر أنني غبي لأنني لم أتمكن من رؤيته :-)".

القطع المفقودة

MCSP ليست حتى مشكلة التعقيد التلوي الوحيدة التي حفزت اختراقًا كبيرًا. في عام 2020 ، أجرى خبير التشفير في كورنيل تك رافائيل باس وطالبه المتخرج ياني ليو اكتشف اتصال بين مشكلة التعقيد التلوي المختلفة وبروتوكول التشفير الأساسي الذي يحدد الحدود بين Heuristica و Pessiland ، أسوأ ما في عوالم Impagliazzo (حيث تكون مشاكل NP الكاملة صعبة بالمعنى العادي للحالة ولكن التشفير لا يزال مستحيلاً). هذا يجعل المشكلة التي درسوها مرشحًا رئيسيًا للهجوم على Pessiland ، و أحدث عمل يشير إلى أنه يمكن أن يعمل ضد Heuristica أيضًا.

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

يحذر Hirahara من أن التحديات لا تزال تنتظر الباحثين العازمين على التخلص من العوالم التي استحضرها Impagliazzo منذ 30 عامًا. وقال: "أود أن أقول إنه في مرحلة ما سيتم استبعاد هيوريستيكا وبيسيلاند ، لكنني لست متأكدًا من مدى قربنا".

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

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

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

قال كارموسينو: "إنه أمر رائع حقًا أنه صعب للغاية". "لن أشعر بالملل أبدًا."

ملاحظة المحرر: سكوت آرونسون عضو في مجلة كوانتاالصورة المجلس الاستشاري.