NL (סיבוכיות)

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

בעיות ב-NL

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

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

ידוע כיום שNL מוכלת בP מאחר שיש רדוקציה פולינומית בזמן ל-2-satisfiability. עם זאת, לא ידוע האם NL=P או האם NL=L. ידוע שNL=co-NL כאשר co-NL היא מחלקת השפות שהשפה המשלימה שלהן ב-NL. ניתן לקשר את NL למכונות דטרמיניסטיות המשתמשות במקום מסוים לפי משפט Savitch, לפיו כל אלגוריתם לא דטרמיניסטי ניתן לסימלוץ על ידי מכונת טיורינג דטרמיניסטית תוך שימוש בלכל היותר זיכרון ריבועי בזמן הריצה של האלגוריתם. משימוש במשפט Savitch נובע ש-NL מוכלת ב-SPACE(log^2), או NL מוכלת ב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 עודד גולדרייך. (באנגלית).