هل يمكنك حلها؟ لعبة الكلمة في أحدث علوم الكمبيوتر | الرياضيات
يسلط لغز اليوم الضوء على إحدى النجاحات الساحقة في علوم الكمبيوتر النظرية، وهي نتيجة محيرة للعقل تركت حتى الخبراء في هذا المجال في حالة ذهول.
سنصل إلى هذه النتيجة (نظرية PCP) لاحقًا. ولكن أولا، إلى التحدي!
إنها كلمة لغز. أدلة نمط الكلمات المتقاطعة تشير كل منها إلى عمود عمودي. الإجابة على كل دليل هي كلمة مكونة من ثلاثة أحرف، مكونة من الأحرف الثلاثة التي يشير إليها الدليل.
دعونا نحل هذا معا. حيوان من ثلاث حروف؟ ماذا عن “الخفافيش”؟
في كل مرة نتمكن من تقديم إجابة مقنعة نحصل على نقطة مقابل كل حرف. “بات” يعطينا درجة 3.
الآن دعونا نواصل. إليك طريقة واحدة لإكمال الشبكة.
لاحظ أن هذه الشبكة ليست الحل الكامل. تم الرد على القرائن الثلاثة العليا بشكل كامل. لقد قمت بتسليط الضوء على الأسهم الخضراء من دليل “الفعل”، الذي يشير إلى “الدفع”. لكن القرائن الثلاثة السفلية تم حلها جزئيًا فقط. يشير الطعام إلى “pey” وليس “pea”. ومع ذلك، يمكننا أن نمنح أنفسنا نقطة لأي حرف في إجابة محتملة، لذا فإن كلمة “pey” تمنحنا نقطتين عن الحرفين الصحيحين في كلمة “pea”. مجموع النقاط: 15 نقطة.
إليك كيفية الحصول على الحل الكامل، بحد أقصى 18 درجة. بالطبع، كان “القط” مكانًا أكثر وضوحًا للبدء!
تقول دانا موشكوفيتز، أستاذة علوم الكمبيوتر في جامعة تكساس في أوستن، إن المغزى من هذا اللغز هو أنه “من المقبول الحصول على حل جزئي”. في الواقع، هذا ما يجعل الأمر ممتعًا. الهدف هو الحصول على أعلى درجة ممكنة.
فيما يلي ثلاثة أمثلة، بترتيب الصعوبة المتزايد.
المشكلة 1
المشكلة 2
المشكلة 3
سأعود الساعة 5 مساءً بالمملكة المتحدة مع الحلول الكاملة. (من المحتمل أن يكون هناك العديد من الحلول الكاملة.) وفي الوقت نفسه، لا يوجد أي حرق. يرجى مناقشة الكلمات المفضلة لديك المكونة من ثلاثة أحرف.
[If any enterprising reader wants to make an interactive version of this puzzle, please put the link below.]
إذًا، ما علاقة هذه الألغاز بواحدة من أهم النتائج في علوم الكمبيوتر؟ تحمل مع.
قبل خمسين عاما، اكتشف علماء الكمبيوتر أن العديد من المشاكل التي تحدث بشكل طبيعي، مثل أفضل طريقة لتكديس أحجام مختلفة من الحقائب في صندوق السيارة، تصبح معقدة للغاية بمجرد توسيع نطاقها بحيث تصبح أجهزة الكمبيوتر غير قادرة على حلها في وقت معقول. ومن المثير للدهشة أيضًا أن الحصول على إجابات تقريبية لمشكلات حقيبة السفر هذه أمر صعب بنفس القدر.
والتشبيه مع لغز اليوم هو أن اللغز له حل صحيح، ولكن له أيضًا حلول “تقريبية”. كما رأينا، يمكنك الحصول على درجات كاملة، ويمكنك أيضًا الحصول على درجات جزئية. تخيل أنك ستقوم بتوسيع نطاق هذا النوع من الألغاز باستخدام المزيد من القرائن والحروف والأسهم. يعد التمييز بين الألغاز التي تعطي حلاً مثاليًا وتلك التي تعطي حلاً جزئيًا أمرًا معقدًا للغاية بحيث لا تستطيع أجهزة الكمبيوتر القيام بذلك في أي وقت معقول.
هذا المجال – دراسة “صلابة التقريب” – له ارتباطات عميقة بنظرية PCP، وهي نتيجة مذهلة تتعلق بالبراهين الرياضية. عادة عندما تريد التحقق من برهان رياضي، فإنك تحتاج إلى التحقق منه سطرًا تلو الآخر لمعرفة ما إذا كانت هناك أخطاء. مثلما يحدث عندما يراجع المعلم أعمالك للتأكد من أن كل جزء من الخصم هو خطوة منطقية.
ومع ذلك، توضح نظرية PCP أنك لا تحتاج إلى التحقق من الإثبات سطرًا تلو الآخر للتأكد من عدم وجود أخطاء. بدلاً من ذلك، يمكنك إعادة كتابة الدليل بحيث يمكنك التحقق منه عن طريق الاختيار العشوائي لبتين أو ثلاثة بتات فقط من الدليل والتحقق من هذه البتات فقط، أي التحقق عند نقطتين أو ثلاث نقاط مما إذا كانت البتة إما 0 أو 0. 1. بضع قطع فقط! لأي دليل رياضي!
اللغز أعلاه هو نسخة مبسطة من نظرية PCP، كما تقول دانا موشكوفيتز، التي توصلت إليها كوسيلة لتقديم الموضوع لطلابها. وتضيف: “عمليا جميع النتائج المعروفة لدينا اليوم حول صلابة التقريب تبدأ بنظرية PCP في شكل لغز الكلمة.”
نعم، هذا أمر محير بعض الشيء، لأن كلمة اللغز لا تتعلق في حد ذاتها بالتحقق من البراهين. ومع ذلك، يمكنك رؤية الرابط إذا كنت تعتبر كل كلمة بمثابة “فحص” للحل الكامل.
كانت نظرية PCP (الحروف التي تشير إلى دليل يمكن التحقق منه احتماليًا) تقدمًا نظريًا هائلاً، ويعد بتطبيقات عملية مهمة. على سبيل المثال، يسمح لجهاز كمبيوتر ذو ذاكرة صغيرة بالتحقق بكفاءة عالية من أن جهاز كمبيوتر كبير قد قام بشيء ما بشكل صحيح، مثل، على سبيل المثال، جهاز iPhone يتحقق من سلامة برنامج في السحابة. يتم استخدام هذه التكنولوجيا بالفعل في سلاسل الكتل، كما هو الحال في شركة StarkWare التكنولوجية الإسرائيلية.
إذا كنت تريد معرفة المزيد عن نظرية PCP، فإليك مقالة رائعة بقلم دانا كانت موجودة في XRDS، المجلة الطلابية لجمعية آلات الحوسبة.
أعمل حاليًا كمتواصل علمي مقيم في معهد سيمونز لنظرية الحوسبة، جامعة كاليفورنيا، بيركلي.
لقد قمت بإعداد لغز هنا في أيام الاثنين البديلة منذ عام 2015. أنا دائمًا أبحث عن الألغاز الرائعة. إذا كنت ترغب في اقتراح واحد، راسلني عبر البريد الإلكتروني.
