يرجى إعادة صياغة هذه المقالة باستخدام التنسيق العام لويكيبيديا

إس إل (تعقيد حسابي)

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Arwikify.svg يرجى إعادة صياغة هذه المقالة باستخدام التنسيق العام لويكيبيديا، مثل إضافة الوصلات والتقسيم إلى الفقرات وأقسام بعناوين. (يونيو 2014)


في علم التعقيد الحسابي SL هي قسم المسائل التي يمكن اختصارها لمسألة USTCON بواسطة اختصار سعة موارده لوجاريثمية , وهذه المسألة هي هل يوجد مسار بين الرأسين s و- t في مخطط غير موجه ؟ هذه المسألة حسب التعريف هي SL كاملة .

هذه المسألة هي حالة خاصة من المسألة STCON والتي تُعنى بايجاد مسار بين الرأسين s و- t في مخطط موجه , هذه المسألة الأكثر عمومية هي مسألة NL كاملة .

في أكتوبر 2004 عومِر راين-جولد برهن أنَّ SL=L .

تاريخ[عدل]

SL عرفها كل من لويس وباباديمتروي عام 1982 واللذين كانا يبحثان عن مكان ملائم للمسألة USTCON ووقتها كان أفضل قسم تعقيد هذه المسألة تابعة له هو القسم NL . وقد عرفا آلة تيورنج المتناظرة وبواسطتها عرفا القسم SL وكذلك بينا أن المسألةUSTCON هي مسألة كاملة ل- SL , وقد بينا أيضا أنَّ :  \mbox{L} \subseteq \mbox{SL} \subseteq \mbox{NL} .

في حين أنَّ L هو قسم الالات تيورنج القطعية التي سعة مواردها لوغارثمية , و- NL هو قسم الالات تيورنج غير القطعية التي سعة مواردها لوغاريثمية .

راين-جولد بَيَّن أنه عندما نُحدد الالات تيورنج المتناظرة لتكون سعة مواردها لوغارثمية عندها لها نفس قوة حساب الالات تيورنج العادية .

مسائل كاملة[عدل]

حسب التعريف فان USTCON هي مسألة كاملة وقد تبين ان هناك كثير من المسائل من هذا النوع مثل :

  • هل مخطط ما هو مخطط ثنائي ؟
  • هل يوجد في المخطط بين رأسين k مسارات منفصلة ؟
  • باعطائنا مخطط بحيث أن كل اضلاعه لها اوزان مختلفة , معطى ضلع هل هو تابع للشجرة الممتدة ذات الحد الادنى ؟

بما أن SL=co-SL لذا فان مكمل هذه المسائل أيضا تابع ل-SL وبما أنه بتنا نعلم أن L=SL اذا كل مسألة SL كاملة هي أيضا L كاملة .

نتائج متعلقة ب-SL[عدل]

بما أنه يمكن حل مسألة USTCON بواسطة DFS او BFS لذا فان SL تابعة ل- P , كما أنَّ SL تابعة ل-NL وذلك أننا نستطيع بسهولة حل المسألة بواسطة آلة تيورنج لا قطعية مع سعة موارد ( مساحة) لوغارثمية , والنتيجة الاولى التي هي ليست مفهومة ضمنا كانت مبرهنة سافيتش والتي وضعت SL في القسم ((L2 =SPACE(log2(n , بعد مبرهنة سافيتش لم يكن هنالك اي تقدم حتى عام 1979 حيث تم التوصل إلى أن SL تابعة ل-RLP ولعل ابرز ما كان لاحقا هو في عام 1992 إذ توصل نيسان وسيزيمردي وويدجيرسون إلى خوارزمية تحل مسألة USTCON مع مساحة ((O(log1.5(n وفي عام 1995 نجح نيسان وتاشما في برهنة التالي : co-SL=SL , واخيرا نجح عومر راينجولد في برهنة أن USTCON تابعة ل-L وبهذا فان SL=L .

انظر أيضا[عدل]

مصادر[عدل]