مشاكل المراسلات البريدية

📅 آخر تحديث: ٢٨ يوليو ٢٠٢٦
✍️ نُشر في: ٢٨ يوليو ٢٠٢٦
📷 يحتوي على 32 صور
الموسوعة الحرة

مشكلة مراسلة بوست هي مشكلة قرار غير قابلة للتقرير تم تقديمها بواسطة إميل بوست في عام 1946. [ 1 ] ولأنها أبسط من مشكلة التوقف ومشكلة القرار، فإنها تستخدم غالبًا في إثباتات عدم قابلية التقرير.

تعريف المشكلة

يتركأ{\displaystyle A}ليكن أبجدية تحتوي على رمزين على الأقل. يتكون مدخل المسألة من قائمتين محدودتينα1،...،αشمال{\displaystyle \alpha _{1},\ldots ,\alpha _{N}}وβ1،...،βشمال{\displaystyle \beta _{1},\ldots ,\beta _{N}}من الكلمات أكثرأ{\displaystyle A}يتمثل حل هذه المشكلة في سلسلة من المؤشرات(أناك)1≤ك≤ك{\displaystyle (i_{k})_{1\leq k\leq K}}معك≥1{\displaystyle K\geq 1}و1≤أناك≤شمال{\displaystyle 1\leq i_{k}\leq N}للجميعك{\displaystyle k}بحيث

αأنا1...αأناك=βأنا1...βأناك.{\displaystyle \alpha _{i_{1}}\ldots \alpha _{i_{K}}=\beta _{i_{1}}\ldots \beta _{i_{K}}.}

إذن، تكمن مشكلة القرار في تحديد ما إذا كان هذا الحل موجودًا أم لا.

تعريف بديل

ز:(أنا1،...،أناك)↦αأنا1...αأناك{\displaystyle g:(i_{1},\ldots ,i_{K})\mapsto \alpha _{i_{1}}\ldots \alpha _{i_{K}}}
ح:(أنا1،...،أناك)↦βأنا1...βأناك.{\displaystyle h:(i_{1},\ldots ,i_{K})\mapsto \beta _{i_{1}}\ldots \beta _{i_{K}}.}

وهذا يؤدي إلى تعريف بديل مكافئ غالباً ما يوجد في الأدبيات، والذي بموجبه يمكن اعتبار أي تماثلينز،ح{\displaystyle g,h}تشكل المجالات المشتركة والمجالات المقابلة المشتركة حالة من مشكلة تطابق بوست، والتي تسأل الآن عما إذا كانت هناك كلمة غير فارغةw{\displaystyle w}في المجال بحيث

ز(w)=ح(w){\displaystyle g(w)=h(w)}.

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

[أأب]{\displaystyle {\begin{bmatrix}a\\ab\end{bmatrix}}}

ومجموعة من قطع الدومينو تبدو كالتالي

[بججأ]،[أأب]،[جأأ]،[أبجج]{\displaystyle {{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}}.

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

[أأب]،[بججأ]،[أأب]،[أبجج]{\displaystyle {{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}bc\\ca\end{bmatrix}},{\begin{bmatrix}a\\ab\end{bmatrix}},{\begin{bmatrix}abc\\c\end{bmatrix}}}}.

بالنسبة لبعض مجموعات الدومينو، قد لا يكون العثور على تطابق ممكناً. على سبيل المثال، المجموعة

[أبجأب]،[جأأ]،[أججبأ]{\displaystyle {{\begin{bmatrix}abc\\ab\end{bmatrix}},{\begin{bmatrix}ca\\a\end{bmatrix}},{\begin{bmatrix}acc\\ba\end{bmatrix}}}}.

لا يمكن أن يحتوي على تطابق لأن كل سلسلة علوية أطول من السلسلة السفلية المقابلة لها.

أمثلة على المشكلة

المثال 1

انظر إلى القائمتين التاليتين:

أحد حلول هذه المشكلة هو المتتالية (3، 2، 3، 1)، لأن

α3α2α3α1=ببأ⋅أب⋅ببأ⋅أ=ببأأبببأأ=بب⋅أأ⋅بب⋅بأأ=β3β2β3β1.{\displaystyle \alpha _{3}\alpha _{2}\alpha _{3}\alpha _{1}=bba\cdot ab\cdot bba\cdot a=bbaabbbaa=bb\cdot aa\cdot bb\cdot baa=\beta _{3}\beta _{2}\beta _{3}\beta _{1}.}

علاوة على ذلك، بما أن (3، 2، 3، 1) هو حل، فإن جميع "تكراراته" كذلك، مثل (3، 2، 3، 1، 3، 2، 3، 1)، إلخ؛ أي أنه عندما يوجد حل، يكون هناك عدد لا نهائي من الحلول من هذا النوع المتكرر.

لكن، لو كانت القائمتان تتألفان من فقطα2،α3{\displaystyle \alpha _{2},\alpha _{3}}وβ2،β3{\displaystyle \beta _{2},\beta _{3}}من تلك المجموعات، لم يكن هناك حل (الحرف الأخير من أي سلسلة α ليس هو نفسه الحرف الذي يسبقه، بينما β لا يقوم إلا بإنشاء أزواج من نفس الحرف).

إحدى الطرق الملائمة لعرض مثال على مشكلة مراسلة بوست هي اعتبارها مجموعة من الكتل على النحو التالي:

وجود كمية غير محدودة من كل نوع من أنواع الكتل. وبالتالي، يُنظر إلى المثال أعلاه على أنه

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

المثال 2

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

في هذه الحالة، كل تسلسل من الشكل (1، 2، 2، ...، 2، 3) هو حل (بالإضافة إلى جميع تكراراته):

رسم تخطيطي لإثبات عدم قابلية الحسم

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

بتفصيلٍ أكثر، تكمن الفكرة في أن السلسلة النصية في الأعلى والأسفل تمثل سجلًا تاريخيًا لعمليات حساب آلة تورينج. وهذا يعني أنها ستسرد سلسلة نصية تصف الحالة الابتدائية، تليها سلسلة نصية تصف الحالة التالية، وهكذا حتى تنتهي بسلسلة نصية تصف حالة القبول. تُفصل سلاسل الحالات برمز فاصل (يُكتب عادةً #). ووفقًا لتعريف آلة تورينج، تتكون الحالة الكاملة للآلة من ثلاثة أجزاء:

  • المحتويات الحالية للشريط.
  • الحالة الحالية لآلة الحالة المحدودة التي تشغل رأس الشريط.
  • الموضع الحالي لرأس التسجيل على الشريط.

على الرغم من أن الشريط يحتوي على عدد لا نهائي من الخلايا، إلا أن جزءًا محدودًا منها فقط سيكون غير فارغ. نسجل هذه الخلايا كجزء من حالة النظام. لوصف حالة التحكم المحدود، نُنشئ رموزًا جديدة، مُرقمة من q1 إلى qk ، لكل حالة من حالات آلة الحالة المحدودة k . نُدرج الرمز الصحيح في السلسلة التي تصف محتويات الشريط عند موضع رأس القراءة/الكتابة، مما يُشير إلى كلٍ من موضع رأس القراءة/الكتابة والحالة الحالية للتحكم المحدود. بالنسبة للأبجدية {0,1}، قد تبدو الحالة النموذجية كالتالي:

101101110 q 7 00110.

سيبدو سجل العمليات الحسابية البسيط على النحو التالي:

q 0 101#1 q 4 01#11 q 2 1#1 q 8 10.

نبدأ بهذه الكتلة، حيث x هي سلسلة الإدخال و q 0 هي حالة البداية:

 
q 0 x #

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

أ
أ

لدينا أيضًا قسم لكل انتقال موضع يمكن أن تقوم به الآلة، يوضح كيفية تحرك رأس الشريط، وكيف تتغير الحالة المحدودة، وماذا يحدث للرموز المحيطة. على سبيل المثال، هنا يكون رأس الشريط فوق الرقم 0 في الحالة 4، ثم يكتب الرقم 1 ويتحرك إلى اليمين، لينتقل إلى الحالة 7:

س 4 0
1 س 7

أخيرًا، عندما يصل الجزء العلوي إلى حالة قبول، يحتاج الجزء السفلي إلى فرصة للحاق به وإتمام المطابقة. وللسماح بذلك، نُوسّع الحساب بحيث بمجرد الوصول إلى حالة قبول، تتسبب كل خطوة لاحقة في الجهاز في اختفاء رمز بالقرب من رأس الشريط، واحدًا تلو الآخر، حتى لا يتبقى أي رمز. إذا كانت q f حالة قبول، فيمكننا تمثيل ذلك باستخدام كتل الانتقال التالية، حيث a هو رمز أبجدي للشريط:

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

q f ## نهاية
# نهاية

يوضح هذا كيف يمكن للعبة ألغاز البلاط الثابتة أن تحاكي عملية حسابية لآلة تورينج.

المثال السابق

q 0 101#1 q 4 01#11 q 2 1#1 q 8 10.

يتم تمثيلها كحل لمشكلة مراسلات البريد على النحو التالي:

المتغيرات

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

  • يمكن صياغة المسألة بدلالة التشكلات الأحادية f و g من الأحادية الحرة B * إلى الأحادية الحرة A * حيث B من الحجم n . وتتمثل المسألة في تحديد ما إذا كانت هناك كلمة w في B + بحيث يكون f ( w ) = g ( w ). [ 3 ]
  • الشرط الذي تنص عليه الأبجديةأ{\displaystyle A}يشترط وجود رمزين على الأقل لأن المسألة قابلة للحل إذاأ{\displaystyle A}يحتوي على رمز واحد فقط.
  • يتمثل أحد البدائل البسيطة في تثبيت قيمة n ، أي عدد البلاطات. هذه المسألة قابلة للحل إذا كانت n ≤ 2، [ 4 ] ولكنها تبقى غير قابلة للحل إذا كانت n ≥ 5. من غير المعروف ما إذا كانت المسألة قابلة للحل إذا كانت 3 ≤ n ≤ 4. [ 5 ]
  • تطرح مسألة مراسلات البريد الدائرية سؤالاً حول ما إذا كانت الفهارسأنا1،أنا2،...{\displaystyle i_{1},i_{2},\ldots }يمكن إيجادها بحيثαأنا1⋯αأناك{\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}}وβأنا1⋯βأناك{\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}}الكلمات المترافقة ، أي أنها متساوية بتردد الدوران. هذا النوع غير قابل للتقرير. [ 6 ]
  • أحد أهم متغيرات مسألة التوافق المحدود (PCP) هو مسألة التوافق المحدود (Post correspondence problem )، التي تتساءل عما إذا كان بالإمكان إيجاد تطابق باستخدام ما لا يزيد عن k من البلاطات، بما في ذلك البلاطات المكررة. يحل البحث الشامل هذه المسألة في زمن O(2^ k )، ولكن قد يصعب تحسين هذا الزمن، لأن المسألة مصنفة ضمن فئة NP-complete . [ 7 ] على عكس بعض مسائل NP-complete مثل مسألة الإرضاء المنطقي ، فقد ثبت أن أحد المتغيرات البسيطة للمسألة المحدودة هو مسألة NP-complete أيضًا، مما يعني أنها تظل صعبة حتى لو تم اختيار المدخلات عشوائيًا (فهي صعبة في المتوسط ​​على المدخلات الموزعة توزيعًا منتظمًا). [ 8 ]
  • هناك نوع آخر من مشكلة PCP يُسمى مشكلة المراسلة البريدية المميزة ، حيث كلαأنا{\displaystyle \alpha _{i}}يجب أن تبدأ برمز مختلف، وكلβأنا{\displaystyle \beta _{i}}يجب أن يبدأ أيضًا برمز مختلف. وقد أثبت كلٌّ من هالافا وهيرفينسالو ودي وولف أن هذا التباين قابل للحسم في زمن أُسّي . علاوة على ذلك، أثبتوا أنه إذا تم تخفيف هذا الشرط قليلًا بحيث يكفي أن يختلف أحد الحرفين الأولين فقط (ما يُعرف بمسألة تطابق بوست ذات العلامتين)، فإن المسألة تصبح غير قابلة للحسم مرة أخرى. [ 9 ]
  • تضيف مسألة التناظر اللاحق القيد الإضافي التالي لكل زوج:(αأنا،βأنا){\displaystyle (\alpha _{i},\beta _{i})}زوج(βأنا،αأنا)=(αج،βج){\displaystyle (\beta _{i},\alpha _{i})=(\alpha _{j},\beta _{j})}وهو موجود أيضاً. هذا المتغير غير قابل للحسم. [ 10 ]
  • مشكلة تضمين المنشورات هي شكل آخر من أشكال البحث عن الفهارس.أنا1،أنا2،...{\displaystyle i_{1},i_{2},\ldots }بحيثαأنا1⋯αأناك{\displaystyle \alpha _{i_{1}}\cdots \alpha _{i_{k}}}هي كلمة فرعية (متناثرة) منβأنا1⋯βأناك{\displaystyle \beta _{i_{1}}\cdots \beta _{i_{k}}}هذا النوع من المسائل سهل الحسم، لأنه عندما توجد بعض الحلول، يوجد على وجه الخصوص حل بطول واحد. أما مسألة تضمين المنشورات المنتظمة فهي أكثر إثارة للاهتمام ، وهي نوع آخر يبحث فيه المرء عن حلول تنتمي إلى لغة منتظمة معينة (مقدمة، على سبيل المثال، في شكل تعبير منتظم على المجموعة).{1،...،شمال}{\displaystyle \{1,\ldots ,N\}}لا تزال مسألة تضمين المنشورات المنتظمة قابلة للحل، ولكن بسبب القيد المنتظم المضاف، فإن تعقيدها مرتفع للغاية لدرجة أنه يهيمن على كل دالة تكرارية متعددة. [ 11 ]
  • تُطرح مسألة تطابق الهوية (ICP) لسؤال ما إذا كان بإمكان مجموعة منتهية من أزواج الكلمات (على أبجدية مجموعة) توليد زوج هوية من خلال سلسلة من عمليات الربط. هذه المسألة غير قابلة للحل، وهي مكافئة لمسألة المجموعة التالية: هل شبه المجموعة المولدة بواسطة مجموعة منتهية من أزواج الكلمات (على أبجدية مجموعة) هي مجموعة؟ [ 12 ]
  • تمت دراسة هذه المسألة في سياق المجموعات، باستخدام صياغة مشابهة للغة مورفيزم المونويد . تأخذ مسألة التناظر للمجموعات لبوست كمدخل زوجًا من تشاكلات المجموعات.و،ز:F(ب)→جي{\displaystyle f,g:F(B)\to G}من المجموعة المجانيةF(ب){\displaystyle F(B)}إلى المجموعةجي{\displaystyle G}ويحاول تحديد ما إذا كانت هناك كلمةw{\displaystyle w}فيF(ب){\displaystyle F(B)}بحيثو(w)=ز(w)≠1{\displaystyle f(w)=g(w)\neq 1}من المعروف أنه قابل للحسم عندماجي{\displaystyle G}هي مجموعة عديمة القوة تقريبًا ، وغير قابلة للحسم بالنسبة لـجي{\displaystyle G}مجموعة زائدية . [ 13 ] من المعروف أيضًا أن نظير مسألة التناظر بوست المميزة قابل للتقرير بالنسبة للمجموعات. [ 14 ]

مراجع

  1. ↑ إي إل بوست (1946). "صيغة مختلفة لمسألة غير قابلة للحل بشكل متكرر" (ملف PDF) . نشرة الجمعية الأمريكية للرياضيات 52 (4): 264-269 . doi : 10.1090/s0002-9904-1946-08555-9 . S2CID 122948861 . 
  2. ↑ مايكل سيبسر (2005). "مسألة بسيطة غير قابلة للحل". مقدمة في نظرية الحوسبة ( الطبعة الثانية). تومسون كورس تكنولوجي. الصفحات 199-205 . ISBN   0-534-95097-3.
  3. ↑ سالوما، أرتو (1981). جواهر نظرية اللغة الرسمية . دار نشر بيتمان. الصفحات 74-75 . ISBN  0-273-08522-0. Zbl 0487.68064 . 
  4. ↑ إهرنفويشت، أ .؛ كارهوماكي، ج .؛ روزنبرغ، ج. (نوفمبر 1982). "مسألة المراسلات (المعممة) مع قوائم تتكون من كلمتين قابلة للتقرير" . علوم الحاسوب النظرية . 21 (2): 119-144 . doi : 10.1016/0304-3975(89)90080-7 .
  5. ↑ ت. نيري (2015). "عدم الحسم في أنظمة الوسوم الثنائية ومشكلة التطابق اللاحق لخمسة أزواج من الكلمات" . في: إرنست دبليو. ماير ونيكولاس أولينجر (محرران). الندوة الدولية الثانية والثلاثون حول الجوانب النظرية لعلوم الحاسوب . STACS 2015. المجلد 30. شلوس داغشتول - مركز لايبنيتز للمعلوماتية. الصفحات 649-661 . doi : 10.4230/LIPIcs.STACS.2015.649 .  
  6. ↑ ك. روهونين (1983). "حول بعض صيغ مسألة بوست للمراسلة". مجلة أكتا إنفورماتيكا . 19 (4). سبرينغر: 357-367 . doi : 10.1007/BF00290732 . S2CID 20637902 . 
  7. ↑ مايكل ر. غاري ؛ ديفيد س. جونسون ( 1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. ص 228. ISBN  0-7167-1045-5.
  8. ↑ ي. غوريفيتش (1991). "اكتمال الحالة المتوسطة" (ملف PDF) . مجلة علوم الحاسوب والأنظمة 42 (3). إلسيفير ساينس: 346-398 . doi : 10.1016/0022-0000(91)90007-R . hdl : 2027.42/29307 .
  9. ↑ ف. هالافا؛ م. هيرفينسالو؛ ر. دي وولف (2001). "مسألة PCP الموسومة قابلة للتقرير". مجلة علوم الحاسوب النظرية 255 ( 1-2 ) . دار نشر إلسيفير للعلوم: 193-204 . doi : 10.1016/S0304-3975(99)00163-2 .
  10. ↑ جيه سي بيرجيت؛ إيه إل تالامبوتسا (2022). "مسألة التناظر اللاحق، وتصويبات لمسألة الحرية لمجموعات المصفوفات شبهية". المجلة الدولية للجبر والحوسبة . 32 (06): 1261-1274 . doi : 10.1142/S0218196722500540 .
  11. ↑ ب. شامبار؛ ف. شنوبيلين (2007). مشكلة التضمين اللاحق ليست بدائية تكرارية، مع تطبيقات على أنظمة القنوات (ملف PDF) . سلسلة محاضرات في علوم الحاسوب. المجلد 4855. سبرينغر. الصفحات 265-276 . doi : 10.1007/978-3-540-77050-3_22 . ISBN   978-3-540-77049-7.
  12. ↑ بول سي. بيل؛ إيغور بوتابوف (2010). "حول عدم قابلية حسم مسألة تطابق الهوية وتطبيقاتها على أنصاف الزمر اللفظية والمصفوفية". المجلة الدولية لأسس علوم الحاسوب . 21 (6). وورلد ساينتيفيك: 963-978 . arXiv : 0902.1975 . doi : 10.1142/S0129054110007660 .
  13. ↑ لورا سيوبانو؛ أليكس ليفين؛ آلان د. لوغان (2024). "مسألة بوست للمراسلة للمجموعات الزائدية والمجموعات شبه الصفرية". نشرة جمعية لندن الرياضية . 56 (1). وايلي: 159-175 . arXiv : 2211.12158 . doi : 10.1112/blms.12921 .
  14. ↑ لورا سيوبانو؛ آلان د. لوغان (2020). "مشكلة تطابق بوست والمعادلات لبعض التشكلات الحرة للمجموعات والوحدات الأحادية". المؤتمر الدولي السابع والأربعون حول الأوتوماتا واللغات والبرمجة . ICALP 2020. المجلد 168. قصر داغشتول. مركز لايبنتز للمعلومات، فاديرن. الصفحات 120:1–120:16. arXiv : 2002.07574 . doi : 10.4230/LIPIcs.ICALP.2020.120 .