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