קיימות מספר בעיות אשר ידועות כ-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 מוכלת ב-formula_4, או formula_5.
זו ההכללה החזקה ביותר של מכונות דטרמיניסטיות במקום מאז 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, ניקח אלגוריתם NL ונבחר מסלול חישוב רנדומלי באורך n, ונבצע זאת 2"n" פעמים. מאחר שאין מסלול חישוב שאורכו n, ומאחר ויש 2"n" מסלולי חישוב לכל היותר, יש סיכוי טוב לבחור במסלול מקבל.
הבעיה היחידה היא שלא ניתן לאחסן מונה עד 2"n" במקום לוגריתמי. לכן נחליף את המונה במונה רנדומלי אשר יטיל n מטבעות הוגנים, ואם כולם נחתו על הראש, יעצור וידחה. מאחר שההסתברות למאורע היא 2-n, תוחלת מספר צעדי המכונה עד לעצירה הוא 2"n". כדי לבצע את האלגוריתם המדובר, יש לשמור מונה של מספר המטבעות שנפלו על ראש. מאחר שיש n מטבעות, נדרש מקום לוגריתמי לאחסון המונה.
ממשפט אימרמן, לפי NL סגורה תחת משלים, ניתן להחליף את השגיאה החד צדדית בחישובים הסתברותיים אלו באפס שגיאה. לכן, בעיות אלו ניתנות לפתרון על ידי מכונות טיורינג הסתברותיות תוך שימוש במקום לוגריתמי וללא טעויות. מחלקת הסיבוכיות המתאימה אשר דורשת גם כן שימוש בזמן פולינומי נקראת ZPLP.
לכן, כאשר מסתכלים על סיבוכיות מקום בלבד, נראה שאלגוריתמים הסתברותיים ואלגוריתמים לא דטרמיניסטיים הם שווי כוח.
גידו בוכוואלד
גידו בוכוואלד (בגרמנית: Guido Buchwald, נולד ב-24 בינואר 1961 בברלין המערבית) הוא כדורגלן עבר גרמני ששיחק בעיקר בשטוטגרט ובנבחרות גרמניה המערבית וגרמניה בעמדת הבלם.
קריירת מועדונים.
שטוטגרטר קיקרס.
בוכוואלד שיחק בקבוצת הנוער של שטוטגרטר קיקרס, ובשנת 1979, עלה ממנה לקבוצת הבוגרים בגיל 18. בוכוואלד שיחק בשטוטגרטר קיקרס במשך ארבע עונות, בהן צבר 146 הופעות והבקיע 18 שערים.
שטוטגרט.
בשנת 1983 עבר בוכוואלד ליריבה העירונית של שטוטגרטר קיקרס, שטוטגרט, והחל קריירה מפוארת שנמשכה 11 שנים, בהן צבר 325 הופעות והבקיע 28 שערים בבונדסליגה. בוכוואלד זכה עם שטוטגרט בשתי אליפויות הבונדסליגה. הראשונה בשנת 1984, והשנייה בשנת 1992, כאשר בוכוואלד הבקיע שער במחזור האחרון מול באייר לברקוזן שש דקות לתום המשחק, שהתברר כשער שהעניק לשטוטגרט את תואר האליפות.
אוראווה רד דיימונדס וקרלסרוהה.
בשנת 1994 עזב בוכוואלד את שטוטגרט ועבר לליגת העל היפנית שהייתה ליגה חדשה באותה תקופה. בוכוואלד חתם באוראווה רד דיימונדס מהעיר סאיטאמה, בצוותא עם חברו לנבחרת גרמניה לשעבר, אובה ביין. בוכוואלד שיחק בקבוצה היפנית שלוש עונות, והבקיע 11 שערים ב-127 הופעות. בשנת 1997 חזר בוכוואלד לליגת הבונדסליגה וחתם בקרלסרוהה, שם שיחק שתי עונות. בעונה הראשונה סיים עם הקבוצה במקום השישי שהקנה מקום בגביע אופ"א בעונה העוקבת, אך לא הצליח לסייע לקבוצה להינצל מירידה בעונה השנייה, שבסופה פרש ממשחק פעיל, בשנת 1999.
קריירה בינלאומית.
בוכוואלד שיחק עשר שנים בנבחרות של גרמניה, החל משנת 1984. תחילה שיחק בנבחרת גרמניה המערבית, ולאחר איחוד גרמניה עבר לשחק בנבחרת גרמניה. בשנת 1984 ייצג בוכוואלד את גרמניה המערבית ביורו 1984, בו לא עברה הנבחרת את שלב הבתים, ולאחר מכן בטורניר הכדורגל של אולימפיאדת לוס אנג'לס, שם נעצרה הנבחרת ברבע הגמר. למונדיאל 1986 בוכוואלד לא זומן על ידי המאמן פרנץ בקנבאואר, אך כן זומן ליורו 1988 ואחר כך למונדיאל 1990, בו זכה עם נבחרת מערב גרמניה, לאחר ניצחון במשחק הגמר על נבחרת ארגנטינה. בוכוואלד זומן גם ליורו 1992, בו סיימה נבחרת גרמניה המאוחדת במקום השני לאחר הפסד בגמר לנבחרת דנמרק, ולמונדיאל 1994, בו הודחה נבחרת גרמניה ברבע הגמר לאחר הפסד לנבחרת גרמניה. לאחר טורניר זה פרש בוכוואלד מהנבחרת, לאחר שצבר 76 הופעות בהן כבש ארבעה שערים.
לאחר הפרישה.
לאחר פרישתו ממשחק, התנסה בוכוואלד באימון, וחזר לאוראווה רד דיימונדס, שם אימן בין השנים 2004-2006 בהצלחה רבה, וזכה באליפות יפן, בשני גביעים ובסופר קאפ אחד, ואף נבחר כמאמן השנה ביפן בשנת 2006. לקראת עונת 2007/08 חתם באלמניה אאכן, היורדת הטרייה מהבונדסליגה, במטרה להחזיר אותה במהירות לבונדסליגה. בוכוואלד פתח את העונה בצורה גרועה ופוטר אחרי חמישה חודשי עבודה. נכון לשנת 2015, בוכוואלד הוא מנהל הכדורגל בקבוצת נעוריו, שטוטגרטר קיקרס.
תארים.
עם שטוטגרט:
עם נבחרת גרמניה המערבית:
תארים אישיים:
תארים כמאמן אוראווה רד דיימונדס:
הרכבת שכבות
הרכבת שכבות (באנגלית: compositing) הוא תהליך בו משלבים אלמנטים מצולמים או מרונדרים שונים לכדי תמונה אחת, עבור יצירת אפקט חזותי. מטרת ההרכבה היא ליצור אשליה שכל המרכיבים בתמונה צולמו ביחד, ואי אפשר להבדיל בין חלקים ממנה שנלקחו ממקורות שונים - אלא נראית רציפה, ריאליסטית ומשכנעת.
תהליך הרכבת השכבות הוא תהליך שמשמש כמעט בכל היבט ביצירת אפקטים חזותיים, בין אם בעת יצירת אלמנט ממוחשב בעצמו, ובין אם שילוב של אלמנט ממוחשב או מצולם בסצנה אחרת. כיום ההרכבה נעשית באופן דיגיטלי, בעזרת תוכנת מחשב.
שיטות ומטרות בסיסיות.
הרכבת שכבות אינה עוסקת רק במיקום אלמנטים זה לצד זה, אלא גם ביחסים ושילובים מורכבים יותר ביניהם, ואינטראקציה לא שגרתית בין שכבות שונות הממוקמות זו על גבי זו. על התכנה בה נעשית הרכבת השכבות לאפשר מתן שקיפות לאלמנטים שונים, יכולת גזירה ועידון קצוות (feathering), והחלת פונקציות אינטראקציה שונות בין צבעים משכבות שונות (blending modes).
סוגים.
קיימים שני סוגים בסיסיים של הרכבת שכבות.
הרכבת שכבות מבוססת יחידות/קישורים/צמתים – היצג גרפי (node-based compositing).
שיטת הרכבת השכבות הגרפית מציגה את האלמנטים השונים, האפקטים וחומרי הגלם בתור יחידות על מפה, המקושרים זה לזה בדרכים שונות. המבנה הכללי בו נעשית העבודה מזכיר מבנה של עץ, אם כי בשונה מעץ, כל יחידה יכולה להיות מקושרת לכמעט כל יחידה אחרת. בסופו של דבר, כל האלמנטים מקושרים זה לזה, ומערכת היחסים המורכבת בין כולם יוצרת תמונה אחת.
הרכבת השכבות הגרפית משמשת בעיקר לשילוב של תמונות/קטעי וידאו מרונדרים (ממוחשבים), שכבר מתאימים זה לזה במיקום ובגודל, וכל שהם דורשים הוא שילוב ו"מעיכה" לכדי תמונה אחת המשלבת את כולם.
הרכבת שכבות מבוססת שכבות.
שיטת הרכבות השכבות הזו מציגה את האלמנטים, אפקטים וחומרי גלם כשכבות שנערמות זו על גבי זו בציר הזמן (timeline). זוהי השיטה המוכרת יותר והוויזואלית יותר להרכבת שכבות, ויכולה לשמש לכמעט כל סוג של הרכבה. בשיטה זו, השכבות נערמות זו על זו בחלון ציר הזמן. אם שכבה נמצאת במקום גבוה יותר מאחרת – היא תופיע בתמונה הסופית מעליה, ו"תדרוס" אותה. לכל שכבה יש אופציות מתוחכמות יותר, כגון שקיפות ופונקציות ערבוב עם השכבות שמתחתיה.
שימושים.
כנאמר, תהליך הרכבת השכבות משמש להיבטים שונים ומרובים בעולם האפקטים החזותיים. להלן דוגמאות מהשימושים המרכזיים והידועים ביותר.
שילוב רנדורים תלת ממדיים.
אפקטים חזותיים תלת ממדיים אינם מרונדרים בפעם אחת ישירות מהתוכנה התלת ממדית, אלא אלמנטים שונים של הסצנה מרונדרים בנפרד. לדוגמה, יהיה רנדור נפרד לטקסטורות, צלליות, הברקות, השתקפות, ועוד. נדרש שילוב בין כל אלה.
הכלי האידיאלי להרכבה זאת הוא תוכנה המאפשרת הרכבת שכבות בהיצג גרפי, משום שאין כאן צורך למשחק עם גדלים ומיקומים של הרינדורים השונים, אלא רק משחק עם יחס הצבעים בין שכבה אחת לאחרת.
מאט פיינטינג (matte painting).