ان ال
در نظریه پیچیدگی محاسباتی اِن‌اِل (NL) به کلاس پیچیدگی مسائلی از مسائل تصمیم‌گیری گفته می‌شود که توسط ماشین تورینگ غیرقطعی و با حافظه لگاریتمی نسبت به اندازه ورودی، قابل حل هستند.
NL تعمیمی از مسائل کلاس اِل است که در مسائل کلاس L مسائلی قرار دارند که با پیچیدگی حافظه لگاریتمی نسبت به اندازه ورودی بر روی ماشین تورینگ قطعی قابل حل هستند. کلاس NL به کمک نمادگذاری NPSPACE نیز قابل تعریف است: formula_1
نتایج مهم در نظریه پیچیدگی کلاس مسائل NL را به برخی از کلاس‌های دیگر مرتبط می‌کند. این در حالی است که رابطه NL با برخی دیگر از کلاس‌ها همچنان به عنوان بعضی از مهم‌ترین مسائل حل نشده در نظریه پیچیدگی مطرح می‌شوند. یکی از این مسائل بررسی برقراری تساوی بین L و NL یا به‌طور دقیق‌تر "آیا formula_2 است؟" می‌باشد.
به کمک تعریف اصلی ماشین تورینگ ساده که تنها دارای یک نوار است، مسائل پیچیدگی فضای لگاریتمی قابل بحث نیستند زیرا اندازه خود ورودی به صورت بدیهی از مرتبه formula_3 است و استفاده از حافظه از مرتبه formula_4 بی‌معنی خواهد بود. به همین دلیل تعریف ماشین تورینگ تغییر پیدا می‌کند.
در این نوع ماشین تورینگ، دو نوار وجود دارد: نوار فقط-خواندنی که روی آن ورودی قرار داده شده‌است و این نوار یک سر دارد که آزادانه روی آن می‌تواند حرکت کند ولی خود نوار غیرقابل تغییر است. نوار دوم هم که نوار خواندن-نوشتن است مانند ماشین تورینگ عادی یک سر دارد و قابلیت خواندن و نوشتن را فراهم می‌کند. با توجه به اینکه بر روی نوار فقط-خواندنی امکان علامت‌گذاری خانه‌های آن و به تبع آن تشخیص دو انتهای چپ و راست نوار وجود ندارد، فرض می‌کنیم که قابلیت تشخیص رسیدن به دو سر نوار برای ماشین تورینگ وجود دارد. حال به کمک این تعریف از ماشین تورینگ، پیچیدگی فضا برابر با تعداد خانه‌های خوانده شده بر روی نوار خواندن-نوشتن تعریف می‌شود و در نتیجه با قرار گرفتن ورودی بر روی نوار فقط-خواندنی، در مسائل کلاس حجمی لگاریتمی، مستقل از نوار ورودی، می‌توان از لگاریتم اندازه ورودی از نوار خواندن-نوشتن استفاده کرد.
یک مبدّل فضای لگاریتمی یک ماشین تورینگ با تعریف اشاره شده در بالا است که در نوار خواندن-نوشتن آن می‌تواند تنها شامل formula_4 نماد باشد. مبدل فضای لگاریتمی M تابع formula_6 است و هنگامی که formula_7 رشته ورودی روی نوار فقط-خواندن باشد، formula_8 رشته باقی‌مانده بر روی نوار خواندن-نوشتن در پایان است. در این صورت formula_9 یک تابع قابل محاسبه در فضای لگاریتمی است.
زبان formula_10 به زبان formula_11 با فضای لگاریتمی قابل کاهش است اگر یک نگاشت قابل کاهش از formula_10 به formula_11 به وسیله یک تابع قابل محاسبه در فضای لگاریتمی مانند formula_9 وجود داشته باشد. نمادگذاری جمله بالا به صورت زیر است:
formula_15
زبان formula_11 یک زبان NL-Complete است اگر
مسائل مشهوری مانند اتصال-ST و 2-ارضاپذیری NL-Complete هستند. در مسئله اتصال-ST به عنوان ورودی یک گراف و دو راس S و T داده می‌شوند و مسئله تصمیم‌گیری وجود داشتن یک مسیر از S به T است. در مسئله 2-ارضاپذیری هم ارضاپذیر بودن یک عبارت منطقی حاصل AND منطقی بین چند عبارت که خود این عبارات نیز از OR شدن 2 متغیر تشکیل شده اند، سؤال می‌شود. نمونه‌ای از عبارات منطقی به شکل زیر است:
formula_20
به دلیل وجود الگوریتم چندجمله‌ای برای حل مسئله 2-ارضاپذیری و با توجه به NL-Complete بودن آن، مجموعه P شامل مجموعه NL می‌شود. این در حالی است که به سوال‌هایformula_21 یا formula_22 هنوز جوابی داده نشده‌است.
در مورد مقایسه NL و co-NL ثابت شده‌است که formula_23. این مسئله در سال 1987 به‌طور مستقل توسط Neil Immerman و Róbert Szelepcsényi ثابت شد که حالت خاصی از قضیه Immerman-Szelepcsényi است که در آن ثابت می‌شود کلاس‌های غیرقطعی پیچیدگی فضا تحت عمل مکمل‌گیری بسته‌اند. این دو نفر در سال 1995 جایزه Gödel را دریافت کردند.
در پیچیدگی مدار NL را می‌توان در سلسله مراتب NC قرار داد. در Papadimitriou 1994، قضیه 16.1 آمده است:
formula_24
همچنین به کمک قضیه ساویچ می‌توان NL را به پیچیدگی فضای کلاس مسائل قطعی مرتبط کرد. طبق قضیه ساویچ هر الگوریتمی را که به صورت غیرقطعی با حافظه معینی پیاده‌سازی شده باشد، می‌توان با حداکثر مربع آن حجم از حافظه به صورت قطعی پیاده‌سازی کرد. نتیجه این قضیه در مورد کلاس NL به صورت زیر می‌شود:
formula_25
طبق آن‌چه که در بالا گفته شد از قضیه Immerman-Szelepcsényi نتیجه می‌شود که NL تحت عملگر مکمل‌گیری بسته است. علاوه بر این NL تحت عملگرهای الحاق و ستاره کلین نیز بسته است.