ان ال

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

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

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

یک مبدّل فضای لگاریتمی یک ماشین تورینگ با تعریف اشاره شده در بالا است که در نوار خواندن-نوشتن آن می‌تواند تنها شامل ${\displaystyle O(logn)}$

زبان ${\displaystyle A}$

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

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

زبان ${\displaystyle B}$

• ${\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}$

در مورد مقایسه NL و co-NL ثابت شده‌است که ${\displaystyle NL=co-NL}$

در پیچیدگی مدار 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 تحت عملگرهای الحاق و ستاره کلین نیز بسته است.