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

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

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

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

تاريخ

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

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

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

مسائل كاملة

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

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

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

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

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

انظر أيضا

• مبرهنة سافيتش
• خوارزمية

مصادر

• http://en.wikipedia.org/wiki/SL_(complexity)