ان ال

در نظریه پیچیدگی محاسباتی اِن‌اِل (NL) (به انگلیسی: Nondeterministic Logarithmic-space) به کلاس پیچیدگی مسائلی از مسائل تصمیم‌گیری گفته می‌شود که توسط ماشین تورینگ غیرقطعی و با حافظه لگاریتمی نسبت به اندازه ورودی، قابل حل هستند.

NL تعمیمی از مسائل کلاس اِل (به انگلیسی: L) است که در مسائل کلاس L مسائلی قرار دارند که با پیچیدگی حافظه لگاریتمی نسبت به اندازه ورودی بر روی ماشین تورینگ قطعی قابل حل هستند. کلاس NL به کمک نمادگذاری NPSPACE نیز قابل تعریف است: ${\displaystyle NL=NPSPACE(logn)}$

نتایج مهم در نظریه پیچیدگی کلاس مسائل NL را به برخی از کلاس‌های دیگر مرتبط می‌کند. این در حالی است که رابطه NL با برخی دیگر از کلاس‌ها همچنان به عنوان بعضی از مهم‌ترین مسائل حل نشده در نظریه پیچیدگی مطرح می‌شوند. یکی از این مسائل بررسی برقراری تساوی بین L و NL یا به‌طور دقیق‌تر آیا ${\displaystyle L=NL}$ است؟ می‌باشد.

ماشین تورینگ مورد بررسی در مسائل پیچیدگی فضا

به کمک تعریف اصلی ماشین تورینگ ساده که تنها دارای یک نوار است، مسائل پیچیدگی فضای لگاریتمی قابل بحث نیستند زیرا اندازه خود ورودی به صورت بدیهی از مرتبه ${\displaystyle O(n)}$ است و استفاده از حافظه از مرتبه ${\displaystyle O(logn)}$ بی‌معنی خواهد بود. به همین دلیل تعریف ماشین تورینگ تغییر پیدا می‌کند.

در این نوع ماشین تورینگ، دو نوار وجود دارد: نوار فقط-خواندنی که روی آن ورودی قرار داده شده‌است و این نوار یک سر دارد که آزادانه روی آن می‌تواند حرکت کند ولی خود نوار غیرقابل تغییر است. نوار دوم هم که نوار خواندن-نوشتن است مانند ماشین تورینگ عادی یک سر دارد و قابلیت خواندن و نوشتن را فراهم می‌کند. با توجه به اینکه بر روی نوار فقط-خواندنی امکان علامت‌گذاری خانه‌های آن و به تبع آن تشخیص دو انتهای چپ و راست نوار وجود ندارد، فرض می‌کنیم که قابلیت تشخیص رسیدن به دو سر نوار برای ماشین تورینگ وجود دارد. حال به کمک این تعریف از ماشین تورینگ، پیچیدگی فضا برابر با تعداد خانه‌های خوانده شده بر روی نوار خواندن-نوشتن تعریف می‌شود و در نتیجه با قرار گرفتن ورودی بر روی نوار فقط-خواندنی، در مسائل کلاس حجمی لگاریتمی، مستقل از نوار ورودی، می‌توان از لگاریتم اندازه ورودی از نوار خواندن-نوشتن استفاده کرد.

مسائل اِن‌اِل-کامل

مبدّل فضای لگاریتمی

یک مبدّل فضای لگاریتمی یک ماشین تورینگ با تعریف اشاره شده در بالا است که در نوار خواندن-نوشتن آن می‌تواند تنها شامل ${\displaystyle O(logn)}$ نماد باشد. مبدل فضای لگاریتمی M تابع ${\displaystyle f:{\sum }^{*}\to {\sum }^{*}}$ است و هنگامی که ${\displaystyle w}$ رشته ورودی روی نوار فقط-خواندن باشد، ${\displaystyle f(w)}$ رشته باقی‌مانده بر روی نوار خواندن-نوشتن در پایان است. در این صورت ${\displaystyle f}$ یک تابع قابل محاسبه در فضای لگاریتمی است.

زبان ${\displaystyle A}$ به زبان ${\displaystyle B}$ با فضای لگاریتمی قابل کاهش است اگر یک نگاشت قابل کاهش از ${\displaystyle A}$ به ${\displaystyle B}$ به وسیله یک تابع قابل محاسبه در فضای لگاریتمی مانند ${\displaystyle f}$ وجود داشته باشد. نمادگذاری جمله بالا به صورت زیر است:

${\displaystyle A{\leq }_{L}B}$

تعریف مسائل اِن‌اِل-کامل

زبان ${\displaystyle B}$ یک زبان NL-Complete است اگر

• ${\displaystyle B\in NL}$ و
• هر زبان مانند ${\displaystyle A}$ که در NL است، با فضای لگاریتمی قابل کاهش به ${\displaystyle B}$ باشد.

مسائل اِن‌اِل-کامل

مسائل مشهوری مانند اتصال-ST و 2-ارضاپذیری NL-Complete هستند. در مسئله اتصال-ST به عنوان ورودی یک گراف و دو راس S و T داده می‌شوند و مسئله تصمیم‌گیری وجود داشتن یک مسیر از S به T است. در مسئله 2-ارضاپذیری هم ارضاپذیر بودن یک عبارت منطقی حاصل AND منطقی بین چند عبارت که خود این عبارات نیز از OR شدن 2 متغیر تشکیل شده اند، سؤال می‌شود. نمونه‌ای از عبارات منطقی به شکل زیر است:

${\displaystyle (x_{1}\vee \neg x_{3})\wedge (\neg x_{2}\vee x_{3})\wedge (\neg x_{1}\vee \neg x_{2})}$

روابط اِن‌اِل با سایر مجموعه‌ها

به دلیل وجود الگوریتم چندجمله‌ای برای حل مسئله 2-ارضاپذیری و با توجه به NL-Complete بودن آن، مجموعه P شامل مجموعه NL می‌شود. این در حالی است که به سوال‌های${\displaystyle NL=P}$ یا ${\displaystyle NL=L}$ هنوز جوابی داده نشده‌است.

در مورد مقایسه NL و co-NL ثابت شده‌است که ${\displaystyle NL=co-NL}$. این مسئله در سال 1987 به‌طور مستقل توسط Neil Immerman و Róbert Szelepcsényi ثابت شد که حالت خاصی از قضیه Immerman-Szelepcsényi است که در آن ثابت می‌شود کلاس‌های غیرقطعی پیچیدگی فضا تحت عمل مکمل‌گیری بسته‌اند. این دو نفر در سال 1995 جایزه Gödel را دریافت کردند.

در پیچیدگی مدار NL را می‌توان در سلسله مراتب NC قرار داد. در Papadimitriou 1994، قضیه 16.1 آمده است:

${\displaystyle {\mathsf {NC_{1}\subseteq L\subseteq NL\subseteq NC_{2}}}}$

همچنین به کمک قضیه ساویچ می‌توان NL را به پیچیدگی فضای کلاس مسائل قطعی مرتبط کرد. طبق قضیه ساویچ هر الگوریتمی را که به صورت غیرقطعی با حافظه معینی پیاده‌سازی شده باشد، می‌توان با حداکثر مربع آن حجم از حافظه به صورت قطعی پیاده‌سازی کرد. نتیجه این قضیه در مورد کلاس NL به صورت زیر می‌شود:

${\displaystyle {\mathsf {NL\subseteq SPACE}}(\log ^{2}n)\ \ \ \ {\text{equivalently, }}{\mathsf {NL\subseteq L}}^{2}}$

ویژگی‌های بسته بودن

طبق آن‌چه که در بالا گفته شد از قضیه Immerman-Szelepcsényi نتیجه می‌شود که NL تحت عملگر مکمل‌گیری بسته است. علاوه بر این NL تحت عملگرهای الحاق و ستاره کلین نیز بسته است.

منابع

• Papadimitriou, C. (1994). "Chapter 16: Logarithmic Space". Computational Complexity. Addison-Wesley. ISBN 0-201-53082-1.
• Michael Sipser (27 June 1997). "Sections 8.4–8.6: The Classes L and NL, NL-completeness, NL equals coNL". Introduction to the Theory of Computation. PWS Publishing. pp. 294&ndash, 302. ISBN 0-534-94728-X.
• Introduction to Complexity Theory: Lecture 7. Oded Goldreich. Proposition 6.1. Our C is what Goldreich calls badRSPACE(log n).