L (التعقيد)

في نظرية التعقيد الحسابي ، يُمثل L (المعروف أيضًا باسم LSPACE أو LOGSPACE أو DLOGSPACE ) فئة التعقيد التي تحتوي على مسائل القرار التي يمكن حلها بواسطة آلة تورينج حتمية باستخدام مساحة ذاكرة قابلة للكتابة بحجم لوغاريتمي . ^{[ 1 ] [ 2 ]} رسميًا، تحتوي آلة تورينج على شريطين ، أحدهما يُشفّر المدخلات ولا يمكن قراءته إلا ^{[ 3 ]،} بينما الشريط الآخر ذو حجم لوغاريتمي ولكنه قابل للكتابة والقراءة. تكفي المساحة اللوغاريتمية لتخزين عدد ثابت من المؤشرات إلى المدخلات ^{[ 1 ]} وعدد لوغاريتمي من العلامات المنطقية، وتستخدم العديد من خوارزميات المساحة اللوغاريتمية الأساسية الذاكرة بهذه الطريقة.

كل مشكلة غير تافهة في L كاملة في ظل اختزالات مساحة اللوغاريتم ، ^{[ 4 ]} لذلك هناك حاجة إلى اختزالات أضعف لتحديد مفاهيم ذات معنى لـ L - الاكتمال، وأكثرها شيوعًا هي اختزالات الدرجة الأولى .

أظهرت نتيجة توصل إليها عمر رينغولد عام 2004 أن مسألة USTCON ، وهي مسألة ما إذا كان هناك مسار بين رأسين في رسم بياني غير موجه معين ، تنتمي إلى L ، مما يدل على أن L = SL ، لأن USTCON مسألة كاملة من فئة SL . ^{[ 5 ]}

إحدى نتائج ذلك هي توصيف منطقي بسيط للغة L : فهي تحتوي تحديدًا على اللغات التي يمكن التعبير عنها باستخدام منطق الرتبة الأولى مع إضافة عامل إغلاق تبادلي متعدٍ (في مصطلحات نظرية الرسوم البيانية ، يحوّل هذا كل مكون متصل إلى زمرة ). لهذه النتيجة تطبيقات على لغات استعلام قواعد البيانات : يُعرَّف تعقيد بيانات الاستعلام بأنه تعقيد الإجابة على استعلام ثابت مع اعتبار حجم البيانات هو المدخل المتغير. وفقًا لهذا المقياس، فإن الاستعلامات الموجهة إلى قواعد البيانات العلائقية ذات المعلومات الكاملة (التي لا تحتوي على مفهوم القيم الفارغة ) كما هو معبر عنه، على سبيل المثال، في الجبر العلائقي، تنتمي إلى لغة L.

تُعدّ L فئة فرعية من NL ، وهي فئة اللغات القابلة للتقرير في فضاء لوغاريتمي على آلة تورينغ غير حتمية . يمكن تحويل مسألة في NL إلى مسألة إمكانية الوصول في رسم بياني موجه يُمثل حالات وانتقالات الحالة للآلة غير الحتمية، ويشير حد الفضاء اللوغاريتمي إلى أن هذا الرسم البياني يحتوي على عدد كثير الحدود من الرؤوس والحواف، ومن ثمّ فإن NL مُحتواة في فئة التعقيد P للمسائل القابلة للحل في وقت كثير الحدود حتمي. ^{[ 6 ]} وبالتالي ، L  ⊆ NL ⊆ P. ويمكن إثبات احتواء L في P بشكل مباشر: لا يمكن لآلة تقرير تستخدم فضاء O (log n ) أن تستغرق أكثر من ^{2O (log n )} = nO ⁽¹⁾ من الوقت، لأن هذا هو العدد الإجمالي للتكوينات الممكنة ^.       

ترتبط الفئة L بالفئة NC على النحو التالي: NC ¹  ⊆ L ⊆ NL ⊆ NC ^2. بعبارة أخرى، إذا كان لدينا حاسوب متوازٍ C يحتوي على عدد متعدد الحدود O ( nk ⁾ من المعالجات لثابت k ما ، فإن أي مسألة يمكن حلها على C في زمن O (log n ) تنتمي إلى L ، وأي مسألة في L يمكن حلها في زمن O (log ²ⁿ ) على C.       

مشكلة لم تُحل في علوم الحاسوب

⁠${\displaystyle {\mathsf {L}}{\overset {?}{=}}{\mathsf {P}}}$⁠

المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

تشمل المسائل المفتوحة المهمة ما إذا كان L  = P ، ^{[ 2 ]} وما إذا كان L = NL . ^{[ 7 ]} بل إنه من غير المعروف حتى ما إذا كان L = NP . ^{[ 8 ]}     

الفئة ذات الصلة من مسائل الدوال هي FL . غالبًا ما تُستخدم FL لتعريف اختزالات فضاء اللوغاريتم .

وكما أن لـ P عدة نسخ عشوائية: BPP و ZPP و PP و RP ، فإن هناك عدة نسخ عشوائية من L.

يُعرَّف احتمال الخطأ المحدود L ( BPL ) مثل BPP ، على أنه فئة تعقيد المشكلات القابلة للحل باستخدام آلة تورينج ذات فضاء لوغاريتمي بحيث:

• وبخلاف الأشرطة المعتادة لآلة تورينج ذات الفضاء اللوغاريتمي، فإن الآلة تأخذ أيضًا شريطًا مليئًا بالبتات العشوائية.
• تكون عملية التوليد العشوائي للقيم للقراءة فقط وفي اتجاه واحد. أي أن رأس القراءة على الشريط العشوائي لا يمكنه التحرك إلا في اتجاه واحد. وللرجوع إلى بت عشوائي سابق، يجب على الجهاز تخزينه في شريط العمل.
• يتعين على آلة تورينج أن تتوقف عند كل مدخل وكل شريط عشوائي.
• إذا كانت الإجابة "نعم"، فإن الجهاز يقبل باحتمالية لا تقل عن 2/3. وإذا كانت الإجابة "لا"، فإن الجهاز يرفض باحتمالية لا تقل عن 2/3.

وهو موجود في NC ² ، والذي هو موجود ^في P. [ ^{9 ]}

يُعرَّف BP•L بنفس تعريف BPL ، باستثناء أن الجهاز يُسمح له بقراءة الشريط العشوائي في الاتجاهين الأمامي والخلفي. وهو يحتوي على BPL . كما أنه يُساوي تمامًا فئة اللغات التي تُقارب فضاء اللوغاريتم: تُعتبر اللغة قريبة من فضاء اللوغاريتم إذا كانت، ^{بالنسبة} إلى كل أوراكل تقريبًا، تنتمي إلى L. ^{[ 10} ]

يُعرَّف ZP•L بنفس تعريف BP•L ، باستثناء أن الجهاز قد يُخرج "غير معروف"، ويجب ألا يُخطئ أبدًا (أي يقبل الإجابة "لا"، والعكس صحيح). العلاقة بين ZP•L و BP•L هي نفسها العلاقة بين ZPP و BPP . فهو يحتوي على BPL ويحتوي على BP•L . ^{[ 10 ]}

يتم تعريف L العشوائي ( RL ) على النحو التالي: BPL :

• وبخلاف الأشرطة المعتادة لآلة تورينج ذات المساحة اللوغاريتمية، فإن الآلة تأخذ أيضًا شريطًا أحادي الاتجاه للقراءة فقط مملوءًا ببتات عشوائية.
• يتعين على آلة تورينج أن تتوقف عند كل مدخل وكل شريط عشوائي.
• إذا كانت الإجابة "نعم"، فاقبلها باحتمالية لا تقل عن 1/2.
• إذا كانت الإجابة "لا"، فارفض دائماً.

كذلك، يجب أن يعمل دائمًا في وقت متعدد الحدود (وإلا فسنحصل على NL ⁾ . ويُشتبه بشدة في أن RL = L. [ ^{11 ]}

يحتوي كل من BPL و RL على فئة ستيف . ^{[ 12 ]}

للدالة الاحتمالية L ( PL ) نفس العلاقة مع L التي تربط PP بـ P :

• إذا كانت الإجابة "نعم"، فاقبلها باحتمالية لا تقل عن 1/2.
• إذا كانت الإجابة "لا"، فارفض باحتمالية لا تقل عن 1/2.

يحتوي على BPL ، ويتم احتواؤه ^بواسطة NC ^{2. [ 13} ]

L منخفض بالنسبة لنفسه، لأنه يستطيع محاكاة استعلامات أوراكل في مساحة السجل (بمعنى أدق، "استدعاءات الوظائف التي تستخدم مساحة السجل") في مساحة السجل، مع إعادة استخدام نفس المساحة لكل استعلام.

الفكرة الرئيسية لـ logspace هي أنه يمكن تخزين رقم ذي مقدار متعدد الحدود في logspace واستخدامه لتذكر المؤشرات إلى موضع الإدخال.

لذا، يُعدّ صنف logspace مفيدًا لنمذجة العمليات الحسابية التي يكون فيها المُدخل كبيرًا جدًا بحيث لا يتسع في ذاكرة الوصول العشوائي (RAM ) للحاسوب. تُعدّ تسلسلات الحمض النووي الطويلة وقواعد البيانات أمثلة جيدة على المشكلات التي يكون فيها جزء ثابت فقط من المُدخل موجودًا في ذاكرة الوصول العشوائي في وقت مُحدد، وحيث لدينا مؤشرات لحساب الجزء التالي من المُدخل المراد فحصه، وبالتالي استخدام ذاكرة لوغاريتمية فقط.

• L/poly ، وهو نوع غير منتظم من L يجسد تعقيد برامج التفرع ذات الحجم متعدد الحدود

• أرورا، سانجيف؛ باراك، بواز (2009). التعقيد الحسابي: منهج حديث . مطبعة جامعة كامبريدج . ISBN 978-0-521-42426-4. Zbl 1193.68112 . 
• باباديميتريو، كريستوس (1993). التعقيد الحسابي (  الطبعة الأولى). أديسون ويسلي. الفصل 16: الفضاء اللوغاريتمي، الصفحات  395-408. ISBN 0-201-53082-1.
• سيبسر، مايكل (1997). مقدمة في نظرية الحوسبة . دار نشر PWS. القسم 8.4: الفئتان L وNL، الصفحات  294-296. ISBN 0-534-94728-X.
• غاري، إم آر ؛ جونسون، دي إس (1979). الحواسيب والاستعصاء: دليل لنظرية اكتمال NP . دبليو إتش فريمان. القسم 7.5: الفضاء اللوغاريتمي، الصفحات  177-181 . ISBN 0-7167-1045-5MR 0519066 . OCLC 247570676 .​  
• كوك، ستيفن أ .؛ ماكنزي، بيير (1987). "مسائل كاملة للفضاء اللوغاريتمي الحتمي" (ملف PDF) . مجلة الخوارزميات . 8 (3): 385-394 . doi : 10.1016/0196-6774(87)90018-6 . ISSN 0196-6774 .