ان ال

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

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

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

زبان های دیگر