NL (סיבוכיות)

בתורת הסיבוכיות, NL (לא דטרמיניסטי עם מקום לוגריתמי) היא מחלקת סיבוכיות המכילה בעיות אשר ניתנות להכרעה על ידי מכונת טיורינג לא דטרמיניסטית אשר משתמשת בזיכרון לוגריתמי לכל היותר. NL היא הכללה של L, מחלקת הסיבוכיות המכילה בעיות אשר ניתנות להכרעה על ידי מכונת טיורינג דטרמיניסטית אשר משתמשת במקום לוגריתמי. מאחר שכל מכונת טיורינג דטרמיניסטית היא גם מכונת טיורינג לא דטרמיניסטית, נובע ש־L מוכל ב־NL. ניתן להגדיר את NL בצורה פורמלית כ-$NSPACE(log(n))$ כאשר $NSPACE(s(n))$ היא מחלקת כל השפות שניתנות לפתרון על ידי מכונת טיורינג לא דטרמיניסטית תוך שימוש ב- $O(s(n))$ זיכרון.

בעיות ב-NL

קיימות מספר בעיות אשר ידועות כ-NL-שלמות תחת רדוקציה לוגריתמית במקום, ביניהן connectivity ו-2-satisfiability. connectivity היא השאלה האם קיים מסלול בין שני קודקודים בגרף מכוון. 2-satisfiability היא השאלה האם בהינתן נוסחה שבה כל פסוקית היא דיסיונקציה של שני ליטרלים, קיימת השמה למשתנים שהופכת את ערך הנוסחה לאמת.

קשרים עם מחלקות סיבוכיות נוספות

ידוע כיום ש־NL מוכלת ב־P מאחר שיש רדוקציה פולינומית בזמן ל-2-satisfiability. עם זאת, לא ידוע האם NL=P או האם NL=L. ידוע ש־NL=co-NL כאשר co-NL היא מחלקת השפות שהשפה המשלימה שלהן ב-NL (משפט אימרמן). ניתן לקשר את NL למכונות דטרמיניסטיות המשתמשות במקום מסוים לפי משפט Savitch, לפיו כל אלגוריתם לא דטרמיניסטי ניתן לסימלוץ על ידי מכונת טיורינג דטרמיניסטית תוך שימוש בלכל היותר זיכרון ריבועי בזמן הריצה של האלגוריתם. משימוש במשפט Savitch נובע ש-NL מוכלת ב-$SPACE(log^{2}(n))$, או $NL\subseteq L^{2}$. זו ההכללה החזקה ביותר של מכונות דטרמיניסטיות במקום מאז 1994. מאחר שמחלקות המשתמשות במקום גדול יותר לא מושפעות מהגדלת המקום בריבוע, המחלקות הדטרמיניסטיות והלא דטרמיניסטיות במקרים אלו הן זהות. מכאן מגיעה הדוגמה הבאה למשל: PSPACE = NPSPACE.

הגדרות הסתברותיות

תהא C מחלקת סיבוכיות של בעיות כריעות, עבורן קיימת מכונת טיורינג הסתברותית לוגריתמית במקום. מכונה זו לעולם לא מקבלת קלטים אשר לא בשפה, אך דוחה קלטים בשפה בהסתברות לכל היותר 1/3. זו נקראת שגיאה חד צדדית. הקבוע 1/3 הוא שרירותי; כל x בין 0 (כולל 0) ל-1/2 (לא כולל 1/2) יספיק. מכאן נובע ש-C=NL. המחלקה C, בשונה מ-L, אינו מוגבל לזמן ריצה פולינומי. אמנם יש לו מספר פולינומי של קונפיגורציות, אך תוך שימוש באלגוריתם אקראי, הוא יוכל לצאת מלולאה אינסופית. אם מגבילים את C לזמן פולינומי, מקבלים את המחלקה RL, אשר מוכלת ב־NL אך לא ידוע שהיא שווה ל־NL. קיים אלגוריתם פשוט אשר מוכיח ש־C=NL. בבירור C מוכל ב-NL, מאחר ש:

• אם המחרוזת לא בשפה, שניהם דוחים בכל מסלול חישוב.
• אם המחרוזת בשפה, אלגוריתם NL יקבל במסלול חישוב אחד לפחות, ואלגוריתם C יקבל בלפחות 2/3 ממסלולי החישוב.

כדי להראות ש־NL מוכל ב C, ניקח אלגוריתם NL ונבחר מסלול חישוב רנדומלי באורך n, ונבצע זאת 2ⁿ פעמים. מאחר שאין מסלול חישוב שאורכו n, ומאחר ויש 2ⁿ מסלולי חישוב לכל היותר, יש סיכוי טוב לבחור במסלול מקבל. הבעיה היחידה היא שלא ניתן לאחסן מונה עד 2ⁿ במקום לוגריתמי. לכן נחליף את המונה במונה רנדומלי אשר יטיל n מטבעות הוגנים, ואם כולם נחתו על הראש, יעצור וידחה. מאחר שההסתברות למאורע היא 2^-n, תוחלת מספר צעדי המכונה עד לעצירה הוא 2ⁿ. כדי לבצע את האלגוריתם המדובר, יש לשמור מונה של מספר המטבעות שנפלו על ראש. מאחר שיש n מטבעות, נדרש מקום לוגריתמי לאחסון המונה. ממשפט אימרמן, לפי NL סגורה תחת משלים, ניתן להחליף את השגיאה החד צדדית בחישובים הסתברותיים אלו באפס שגיאה. לכן, בעיות אלו ניתנות לפתרון על ידי מכונות טיורינג הסתברותיות תוך שימוש במקום לוגריתמי וללא טעויות. מחלקת הסיבוכיות המתאימה אשר דורשת גם כן שימוש בזמן פולינומי נקראת ZPLP. לכן, כאשר מסתכלים על סיבוכיות מקום בלבד, נראה שאלגוריתמים הסתברותיים ואלגוריתמים לא דטרמיניסטיים הם שווי כוח.

ראו גם

• מחלקת סיבוכיות
• NP (סיבוכיות)

לקריאה נוספת

• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997

קישורים חיצוניים

• Introduction to Complexity Theory: Lecture 7 עודד גולדרייך. (באנגלית).