الاتصال القياسي

في علوم الحاسوب ، تعتبر الاتصالية st أو STCON مشكلة قرار تسأل، بالنسبة للرؤوس s و t في رسم بياني موجه ، ما إذا كان من الممكن الوصول إلى t من s .

بصورة رسمية، تُعطى مشكلة القرار بالصيغة التالية

PATH = { ⟨ D , s , t ⟩   | D هو رسم بياني موجه مع مسار من الرأس s إلى t } .

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

إن مكمل الاتصال st ، والمعروف باسم عدم الاتصال st ، هو أيضًا في فئة NL، لأن NL  =  coNL وفقًا لنظرية Immerman–Szelepcsényi .

على وجه الخصوص، تُعدّ مسألة الاتصال من النوع st مسألةً كاملةً في فئة NL ، أي أن كل مسألة في فئة NL قابلة للاختزال إلى مسألة اتصال في ظل اختزال لوغاريتمي . ويظل هذا صحيحًا حتى في حالة الاختزالات من الرتبة الأولى ( إيمرمان، 1999 ، ص 51) . ويتم الاختزال اللوغاريتمي من أي لغة في NL إلى STCON على النحو التالي: لنفترض وجود آلة تورينغ غير حتمية في الفضاء اللوغاريتمي M تقبل لغةً في NL. بما أن مساحة شريط العمل لوغاريتمية فقط، فإن جميع الحالات الممكنة لآلة تورينغ (حيث تمثل الحالة حالة الآلة الداخلية ذات الحالة المحدودة، وموضع رأس القراءة/الكتابة، ومحتويات شريط العمل) هي حالات متعددة الحدود. نرسم جميع الحالات الممكنة للآلة الحتمية في الفضاء اللوغاريتمي على رؤوس رسم بياني، ونضع حافة بين u و v إذا كان من الممكن الوصول إلى الحالة v من u في خطوة واحدة من الآلة غير الحتمية. الآن، فإن مشكلة قبول الآلة هي نفسها مشكلة وجود مسار من حالة البداية إلى حالة القبول. 

تضمن نظرية سافيتش أنه يمكن محاكاة الخوارزمية في مساحة حتمية O (log ² n ). 

تُسمى المشكلة نفسها بالنسبة للرسوم البيانية غير الموجهة بالاتصالية غير الموجهة st ، وقد أثبت عمر رينغولد أنها تنتمي إلى فئة L. وقد فاز هذا البحث بجائزة غريس موراي هوبر لعام 2005. كان من المعروف سابقًا أن الاتصالية غير الموجهة st كاملة بالنسبة للفئة SL ، لذا أظهر عمل رينغولد أن SL هي نفس فئة L. أما بالنسبة للرسوم البيانية المتناوبة، فإن المشكلة كاملة من الفئة P ( إيمرمان 1999 ، ص 54) .  

• سيبسر، مايكل (2006)، مقدمة في نظرية الحوسبة ، تومسون كورس تكنولوجي، رقم ISBN 0-534-95097-3
• إيمرمان، نيل (1999)، التعقيد الوصفي ، نيويورك: سبرينغر-فيرلاغ، ISBN 0-387-98600-6