חדר ההסבה של הצאר אלכסנדר הראשון עוצב בין השנים 1752–1756 ושימש את הצאר כחדר פרטי. חדר זה יוצא דופן בין חדרי הארמון בכך שקירותיו מחופים במשי סיני. בחדר זה ארונות שבהם מוצגים כלי חרסינה יפנית וסינית לצד פורצלן מברלין.
באגף הצפוני של הארמון מצוי "חדר האוכל הירוק" שתכנן קמרון בשנת 1773, במקום שבו עמד חדר "הגן התלוי" של רסטרלי, עבור הצאר פאבל הראשון ורעייתו. חדר זה מעוטר בירוק ובפסלי גבס מעשה ידי איוואן מארטוס. החדר ניזוק בשריפה בשנת 1820, ושוקם בפיקוחו של סטאסוב.
חדרים נוספים שעיצב קמרון, ובהם חדר המשרתים, חדר האוכל הרשמי הכחול (בו ארובות העשויות שיש קרארה) והחדר הקדמי, וכן חדר השנה של הצאר אלכסנדר הראשון בסגנון פומפיי, ניזוקו אף הם בשריפה בשנת 1820, ושוקמו אחריה.
בשנת 2006 בעיירה ליד סנקט פטרבורג נבנה ארמון וסילייב שהוא העתק של הארמון.
משפט אימרמן
משפט אימרמן (Immerman–Szelepcsényi) הוא תוצאה בתורת הסיבוכיות (ענף במדעי המחשב) המראה כי מחלקות סיבוכיות מקום אי דטרמיניסטיות סגורות לפעולת המשלים (בעוד אותה שאלה עבור סיבוכיות זמן עודנה פתוחה וככל הנראה התשובה לה שלילית). המשפט הוכח בשנת 1987 באופן בלתי תלוי בידי ניל אימרמן ו-Róbert Szelepcsényi, אשר זכו ב-1995 בפרס גדל על תוצאה זו.
באופן פורמלי, תוצאת המשפט היא כי לכל פונקציה formula_1 מתקיים formula_2.
מבוא.
בעיות רבות בהן עוסקת תורת הסיבוכיות ניתנות לניסוח כשאלות כן/לא (למשל, האם מספר הוא ראשוני או לא, האם תוכנית מחשב נתקעת או לא, האם גרף מכיל מעגל המילטוני או לא וכדומה). לכל בעיה ניתן לדבר על הבעיה המשלימה לה - בעיה ששאלותיה הן זהות אך התשובה להן הפוכה. כך למשל הבעיה המשלימה לבעיה "האם מספר הוא ראשוני" היא הבעיה "האם מספר אינו ראשוני", כלומר האם הוא פריק.
אם קיים אלגוריתם דטרמיניסטי לפתרון בעיה, שינוי פשוט הופך אותו לאלגוריתם לפתרון הבעיה המשלימה - תשובת "כן" של האלגוריתם הופכת לתשובת "לא" ולהפך, אך פרט לכך אין צורך לשנות את האלגוריתם - בפרט, כמות המשאבים שדורש האלגוריתם עבור הבעיה המשלימה זהה לכמות המשאבים שדורש האלגוריתם עבור הבעיה המקורית.
תכונה זו אינה נשמרת כאשר עוסקים במודל הרעיוני של אלגוריתם לא דטרמיניסטי. במודל זה, האלגוריתם מסוגל לבצע בחירות בין אפשרויות פעולה רבות, להבדיל מאלגוריתם דטרמיניסטי שתמיד יש לו דרך פעולה אחת ויחידה על קלט מסוים. על כן, לאלגוריתם אי דטרמיניסטי יש חישובים שונים רבים אפשריים על אותו הקלט. כל שנדרש מהאלגוריתם האי דטרמיניסטי הוא לענות "כן" באחד מהחישובים הללו עבור קלט שהתשובה הנכונה עליו היא "כן", ועבור קלטים שהתשובה הנכונה עליהם היא "לא" על האלגוריתם לענות "לא" עבור כל החישובים השונים שלו. חוסר סימטריה זה (חישוב יחיד שבו יש לענות "כן" לעומת הצורך לענות "לא" בכל החישובים) הוא שמונע בניית אלגוריתם אי דטרמיניסטי עבור הבעיה המשלימה באופן דומה לזה שתואר לעיל.
ניתן לקחת כדוגמה לכך את האלגוריתם האי דטרמיניסטי הבודק האם מספר הוא פריק. אלגוריתם אי דטרמיניסטי לבעיה זו פועל כך על קלט formula_3; הוא בוחר מספר formula_4 באופן אי דטרמיניסטי (דהיינו כל חישוב מתאפיין ב-formula_5 אחר השייך לתחום) ובודק האם formula_5 מחלק את formula_3 פשוט על ידי חלוקה. אם formula_5 חילק את formula_3, האלגוריתם עונה "כן", ואחרת הוא עונה "לא". אם formula_3 פריק הרי שקיים formula_11 שמחלק אותו ולכן קיים חישוב שבו האלגוריתם האי דטרמיניסטי יגיד "כן", ואילו אם formula_3 אינו פריק לא קיים formula_5 שכזה ולכן לכל חישוב האלגוריתם יגיד "לא", כנדרש.
נביט על האלגוריתם ה"הפוך" לבעיה זו: האלגוריתם מבצע בדיקה זהה - בוחר formula_5 ובודק האם formula_3 מתחלק בו, ועונה "לא" אם כך הדבר ואחרת עונה "כן". אלא שאלגוריתם זה בבירור אינו אלגוריתם עבור בעיית הראשוניות; אמנם, אם formula_3 ראשוני אז לכל formula_5 שיבחר האלגוריתם יענה "כן", אך אם formula_3 אינו ראשוני עדיין ייתכן שיהיו חישובים שבהם האלגוריתם עונה "כן", אם בחר formula_5 שאינו מחלק את formula_3. למשל, אם נבחר formula_21 שאינו ראשוני, והאלגוריתם בחר formula_22 הוא יענה "כן", אף שהיה עליו לענות "לא".
מכיוון שבהינתן אלגוריתם אי דטרמיניסטי ניתן להמיר אותו תמיד באלגוריתם דטרמיניסטי ולהפך, מובטח כי לכל בעיה הניתנת לפתרון, ואפילו יהא זה פתרון אי דטרמיניסטי, ניתן לפתור גם את הבעיה ההפוכה באופן אי דטרמיניסטי. עם זאת, באופן כללי המרת אלגוריתם אי דטרמיניסטי בדטרמיניסטי מגדילה את כמות משאבי החישוב הנדרשים לפתרון הבעיה. מכאן עולה השאלה האם בהינתן בעיה שקיים לה פתרון אי דטרמיניסטי המשתמש בכמות מסוימת של משאבים קיים פתרון אי דטרמיניסטי לבעיה המשלימה שצורך את אותה כמות משאבים (או לפחות את אותו סדר גודל של כמות משאבים). כאשר שאלה זו מנוסחת עבור המשאב של זמן חישוב יעיל (פולינומי), מתקבלת למעשה השאלה האם המחלקה NP שווה למחלקה co-NP, שהיא שאלה פתוחה חשובה במדעי המחשב. משפט אימרמן עונה על השאלה עבור משאב הזיכרון - הוא מראה כי לכל פונקציה formula_23 "סבירה", אם בעיה ניתנת לפתרון אי דטרמיניסטי בסיבוכיות זיכרון של formula_24 אז גם הבעיה המשלימה ניתנת לפתרון אי דטרמיניסטי בסיבוכיות זיכרון זו. בניסוח פורמלי,
formula_2.
תוצאת המשפט (והוכחתו) מזכירים את משפט סביץ' הפשוט יותר, המראה שכל בעיה הניתנת לפתרון באופן אי דטרמיניסטי בסיבוכיות זיכרון המיוצגת על ידי פונקציה "סבירה" formula_23, ניתן לפתור את הבעיה באופן דטרמיניסטי תוך שימוש בכמות זיכרון של לכל היותר formula_27, ובפרט שאם בעיה ניתנת לפתרון אי דטרמיניסטי תוך שימוש בכמות "יעילה" של זיכרון, היא ניתנת גם לפתרון דטרמיניסטי תוך שימוש בכמות יעילה שכזו של זיכרון. עם זאת, משפט אימרמן אינו תוצאה מיידית של משפט סביץ' שכן הוא "בזבזני" פחות - הוא אינו דורש הגדלה אסימפטוטית כלל של סיבוכיות הזיכרון על מנת לפתור את הבעיה המשלימה.
הוכחה.
בדומה למשפט סביץ', הוכחת המשפט הכללי מסתמכת על פתרון בעיה ספציפית - בעיית הישִיגוּת בגרפים. בהינתן גרף מכוון formula_28 בעל formula_3 צמתים ושני צמתים formula_30, בעיית הישיגות היא השאלה האם קיים מסלול מ-formula_31 אל formula_32 בגרף. מכיוון שניתן לייצג חישוב כלשהו של אלגוריתם אי דטרמיניסטי בתור מסלול בגרף אשר מייצג את הקונפיגורציות האפשריות השונות בחישוב, ניתן לצמצם את השאלה האם האלגוריתם עונה "כן" על קלט מסוים לשאלה אם קיים בגרף הקונפיגורציות שמתאר את ריצתו על קלט זה מסלול מהקונפיגורציה ההתחלתית לקונפיגורציה שבה האלגוריתם עונה "כן" (ניתן להניח ללא הגבלת הכלליות כי קיימת רק אחת כזו).
בעיית הישיגות בגרף ניתנות לפתרון אי דטרמיניסטי בזיכרון formula_33:
ההוכחה למשפט אימרמן מבוססת על כך שגם הבעיה המשלימה - הבדיקה האם בגרף לא קיים מסלול מ-formula_31 אל formula_32 - ניתנת לביצוע באופן אי דטרמיניסטי בזיכרון formula_33. כלומר, קיימת מכונת טיורינג לא-דטרמיניסטית שמקבלת כקלט את צומת המקור formula_31 וצומת היעד formula_32 ועונה "כן" אם formula_32 אינו יָשִׁיג מ-formula_31 (לפחות עבור בחירה אי-דטרמיניסטית יחידה שמבצע האלגוריתם). לעומת זאת אם קיים מסלול formula_31 אל formula_32, האלגוריתם יענה "לא" בכל אחד מהחישובים שהוא מבצע בהתאם לבחירות האי-דטרמיניסטיות.
אימרמן הראה כי אם האלגוריתם יודע מראש מהו מספר הצמתים הישיגים מ-formula_31 לכל היותר ב-formula_49 צעדים (נסמן מספר זה בformula_50), אז האלגוריתם יכול פשוט "לנחש" את אותם צמתים ישיגים (ניחוש של formula_50 צמתים שונים, למשל על ידי מעבר סדרתי על כל הצמתים ובחירה אי דטרמיניסטית אם רוצים לבחור אותו או לא), ופשוט לבדוק האם הם ישיגים מformula_31 (באופן אי-דטרמיניסטי, בזיכרון formula_33, כפי שתואר מעלה). אם אכן האלגוריתם בחר את formula_50 הצמתים ה"נכונים" (אלו שבאמת ישיגים מ-formula_31), הוא בודק האם הצומת formula_32 הוא אחד מהם. אם formula_32 אחד מהצמתים הישיגים, האלגוריתם עונה "לא", ואחרת עונה "כן". אם אחת הבדיקות במהלך הדרך נכשלה האלגוריתם מחזיר תשובה "לא" כברירת מחדל (למשל, היה והוגרל צומת "לא נכון" עבור הקבוצה של formula_50 הצמתים הישיגים).
לפי תיאור האלגוריתם, קל לראות שאם המספר formula_50 ידוע לאלגוריתם, ו-formula_32 אינו יָשיג מ-formula_31, אז קיימת בחירה שבה האלגוריתם יבחר בדיוק את formula_50 הצמתים הישיגים מ-formula_31, יבדוק שכל אחד מהם אכן ישיג, יזהה ש-formula_32 אינו אחד מהם, ויחזיר תשובה "כן"
ואילו כאשר formula_32 ישיג מ-formula_31 (ב-i צעדים), אזי האלגוריתם יחזיר תשובה "לא" עבור כל אחת מהבחירות שהוא יכול לבצע: או שאלגוריתם יכשל באחת מבדיקות הביניים (ואז יחזיר "לא"), או שיצליח בכל הבחירות, יזהה את קבוצת formula_50 הצמתים הישיגים מ-formula_31 (ב-i צעדים), יבדוק שכל אחד מהם אכן יָשיג, ואז יזהה ש-formula_32 ישיג מ-formula_31, ויחזיר תשובה "לא". הבדיקה המתוארת לעיל היא חסכונית מבחינת צריכת הזיכרון שלה - מעבר סדרתי על כל צומתי הגרף דורש רק formula_33 זיכרון, וכך גם הבדיקות הנוספות שתיארנו.
מכאן עולה כי אם נתון המספר formula_72 (הצמתים הישיגים ב-formula_73 צעדים, כאשר formula_73 הוא גודל הגרף), אז ניתן לפתור את הבעיה בזיכרון formula_33 - פשוט מוודאים ש-formula_32 אינו ישיג מ-formula_31 ב-formula_3 צעדים (ולכן אינו ישיג כלל).