مرجع
آخر الزيارات

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

388 كلمة•0 مشاهدة•🗒️ منذ يومين
باختصار: في علم التعقيد الحسابي SL هي قسم المسائل التي يمكن اختصارها لمسألة USTCON بواسطة اختصار سعة موارده لوجاريثمية، وهذه المسألة هي هل يوجد مسار بين الرأسين s و- t في مخطط غير موجه؟. في هذه المقالة 3 أقسام: «مسائل كاملة»، «نتائج متعلقة ب-SL» و«تاريخ».
المحتويات
  1. مسائل كاملة
  2. نتائج متعلقة ب-SL
  3. تاريخ

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

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

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

مسائل كاملة

هل مخطط ما هو مخطط ثنائي؟

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

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

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

هل يوجد في المخطط بين رأسين k مسارات منفصلة؟

نتائج متعلقة ب-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 .

تاريخ

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

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

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

ما رأيك في هذه المقالة؟

📝 هل في هذه المقالة خطأ؟

إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.