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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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