משפט סביץ' מצביע על הקשר בין סיבוכיות הזיכרון של מכונות טיורינג דטרמיניסטיות ואי דטרמיניסטיות (קשר שטרם ידוע דומה לו עבור סיבוכיות זמן):
ממשפט זה נובע, למשל, שאין צורך להגדיר מחלקה מיוחדת NPSPACE בתור המקבילה האי דטרמיניסטית של PSPACE, שכן שתי המחלקות שוות.
משפט Immerman-Szelepcsényi.
משפט Immerman-Szelepcsényi מראה כי מחלקות סיבוכיות זיכרון אי דטרמיניסטיות סגורות למשלים. בניסוח מדויק:
משפטי היררכיה.
משפטי ההיררכיה לזיכרון אומרים, בצורה אינטואיטיבית, שאם מגדילים בצורה אסימפטוטית את כמות הזיכרון האפשרית לפתרון בעיה, מגדילים בכך את אוסף בעיות ההכרעה שניתן לפתור. בניסוח יותר פורמלי:
עבור כמויות נמוכות של זיכרון המצב מורכב יותר. ניתן להראות שאם formula_34 אז formula_35, ובמילים אחרות - אם קיים אלגוריתם שמכריע בעיה באמצעות שימוש בכמות זניחה מאוד של זיכרון יחסית לגודל הקלט - אסימפטוטית פחות מאשר לוגריתם של לוגריתם של גודל הקלט - אז ניתן להסתפק בכמות קבועה של זיכרון. המחלקה formula_36 שקולה לשפות רגולריות, כלומר אלה הפתירות באמצעות אוטומט סופי דטרמיניסטי. כמו כן ניתן להראות בעיות שאינן ניתנות לפתרון בעזרת כמות קבועה של זיכרון אך קיים אלגוריתם בעל סיבוכיות זיכרון של formula_37 לפתרונן, כך שהחסם הדוק.
הקשרים בין מחלקות הסיבוכיות השונות.
המחלקה PSPACE היא גדולה למדי; למשל, היא מכילה הן את המחלקה NP של הבעיות הניתנות לפתרון אי דטרמיניסטי בזמן פולינומי והן את המחלקה PP של הבעיות הניתנות לפתרון הסתברותי בזמן פולינומי. לא ידוע האם PSPACE=NP או אולי אפילו PSPACE=P, אך ממשפטי ההיררכיה לזיכרון עולה ש-PSPACE שונה מ-L. מכך נובע שלפחות הכלה אחת מתוך השרשרת formula_38 חייבת להיות הכלה ממש, אך לא ידוע מהי; הסברה הרווחת היא שכל ההכלות הן הכלות ממש. בשל גודלה של PSPACE, השפות שנמצאות בה אינן נחשבות בהכרח לשפות ש"קל" להכריע; לעומתה, המחלקה L מספקת אפיון שכזה.
בדומה למושג השלמות ב-NP קיים גם מושג דומה של שלמות ב-PSPACE - בעיה היא PSPACE שלמה אם כל שפה ששייכת ל-PSPACE ניתנת לרדוקציה פולינומית אליה. דוגמה לשפה PSPACE שלמה היא השפה TQBF.
תיאטרון באר שבע
תיאטרון באר שבע הוא תיאטרון ישראלי רפרטוארי שנוסד בשנת 1973 בעיר באר שבע.
היסטוריה.
השנים הראשונות.
התיאטרון נוסד כתיאטרון עירוני, בעת כהונתו של אליהו נאווי כראש העירייה, ביוזמת סגן ראש העיר ומחזיק תיק התרבות, בנ"ץ כרמל, זכריה לירז יזם של אירועי תרבות בנגב, ודוד טוביהו ראש העירייה הראשון של באר שבע ומיזמי הקמת אוניברסיטת בן-גוריון. את ההצגה הראשונה ביים תיאודור תומא, תרגום ועיבוד למחזה צרפתי בשם "מתי תחתן עם אשתי".
בשנת 1973, לאחר שהועלו שתי הצגות מונה לתיאטרון מנהל מקצועי, גרי בילו. הוא שימש כמנהלו האמנותי והאדמיניסטרטיבי של התיאטרון במשך שמונה שנים, ופעל להעלאת רמתו ולפעילותו כתיאטרון רפרטוארי המציג הצגות קבועות. בסוף 1974, לאחר הפסקה בעקבות מלחמת יום הכיפורים, פתח התיאטרון את עונתו השנייה, בה הוצגו בין היתר, המחזה "מלקולם הקטן ומלחמתו בסריסים" בבימוי חנן שניר, ו"ביבר הזכוכית" בבימוי עדנה שביט. בעונה זה צוות השחקנים גדל ל-15, והם נדרשו להיות תושבי באר שבע בכדי לשחק בתיאטרון. עם ראשוני שחקני התיאטרון נמנו: נעמי בלומנטל, אתי שילוני, דב'לה רייזר, ששי סעד, שמוליק שילה, יוסי קאנץ, הוגו ירדן, מיכאל רונן, רפי תבור, מרגלית סטנדר, עירית שילה, אילנה ינובסקי, אורה בר-אור ורוברט הניג. מאוחר יותר הצטרף דורון תבורי. במאי הבית הראשון של התיאטרון היה ד"ר דן רונן. עם הקמתו הפעיל התיאטרון תוכנית מנויים שכללה גם את האפשרות לראות הצגות של תיאטראות אחרים שהוצגו בבאר שבע וקונצרטים. בשנים הראשונות רוב תקציב התיאטרון הגיעה מהעירייה, עמותת אמנות לעם של ההסתדרות, ומשרד החינוך והתרבות.
בשנת 1977 היה לתיאטרון כבר 3,000 מנויים עוד 5,000 תלמידי תיכון בעיר שזכו לצפות בהצגות באופן קבוע בחינם. בין המחזות שעלו בשנה זו היו: "בית ברנרדה אלבה" בבימוי יורם פאלק (שכיהן כבמאי הבית בשנים 1976 עד 1981), מחזה מקורי של ערן בניאל, "הרצח של פיירו בבית הספר הריאלי", ו"הלילה השנים עשר של ויליאם שייקספיר בבימוי חנן שניר. בסוף אותה שנה הגיע גדעון זינגר לתיאטרון, להשתתף במחזה "אנדורה" בבימוי תום לוי.
בשנות ה-80.
בשנת 1980 נאלץ התיאטרון לבצע קיצוצים, לאחר שנקלע לגירעון כספי. צוות השחקנים צומצם מ-24 ל-16. בשנת 1985 קיבל התיאטרון מענק מקרן התרבות אמריקה-ישראל.
בשנים 1981–1993 ניהלה את התיאטרון ציפי פינס, שתרמה להתפתחותו. צוות השחקנים בתקופה זו כלל בין היתר את: שרון אלכסנדר, חנה אזולאי הספרי, חגית דסברג ויורם חטב ורבים אחרים. לשחקנים לא הייתה קביעות והם הוחתמו כולם פעם לעונה אחת בלבד. בשנים אלו נהג התיאטרון לערוך הופעות גם באילת. בין ההצגות הבולטות שעלו באותן השנים היו" "לצאת מכאן" של מרשה נורמן (1983), "סיפור אהבה בשלושה פרקים" של הארווי פירסטיין (1984), "אותו ואת בנו" של י"ד ברקוביץ (1986) ומחזה מקורי של שמואל הספרי "גיסתו של גולדין".
בעונת 1988, הצטרפו לצוות התיאטרון השחקנית הוותיקה אלישבע מיכאלי והשחקן משה בקר.
בשנת 1989 העלה לראשונה הפקה משותפת עם תיאטרון בית ליסין, "בורגנים" של מקסים גורקי.
בשנות ה-90 וה-2000.
מ-1993 ניהל אותו גדי רול, ומ-1996 הוא נוהל על ידי רזי אמיתי. בין השנים 2009-2004 ניהל אותו השחקן נתן דטנר. בספטמבר 2009 מונה במקומו שמוליק יפרח ולצידו המנהל האמנותי רפי ניב.
בשנת 2017 מונה סמנכ"ל הכספים של התיאטרון ב-11 השנים האחרונות, אורן אהרוני, לתפקיד מנכ"ל תיאטרון באר-שבע, וכיהן בתפקיד זה עד מאי 2019.
במאי 2019, חזר שמוליק יפרח לתפקיד מנכ"ל תיאטרון באר-שבע ומכהן בתפקיד זה עד היום.
בפברואר 2019 מונתה שיר גולדברג למנהלת אמנותית במקומו של ניב.
מבנה התיאטרון.
לאורך השנים הועלו הצגות התיאטרון ב"בית העם" (בו שוכן כיום גודמן - בית ספר למשחק בנגב), וכשהורחבה הפעילות הועלו חלק מההצגות גם ב"מרכז הצעירים" ובהיכל התרבות באר שבע. בשנת 2008 עבר התיאטרון למבנה חדש, המשכן לאמנויות הבמה באר שבע בתכנון האדריכל סלו הרשמן, בו פועלת גם הסינפונייטה הישראלית באר שבע ונערכים מופעים וכנסים מגוונים. במבנה יש שני אולמות, האחד מכיל למעלה כ-900 מקומות והשני מכיל כ-420 מקומות.
פעילות.
התיאטרון מציג בכל עונה 7-5 הצגות, מקוריות וקלאסיות. בתיאטרון מוצגות הצגות רפרטואר, הצגות חוץ (מתיאטראות אחרים), הצגות מקוריות והצגות ילדים. ההצגות המקוריות מוצגות גם בתיאטראות אחרים ברחבי הארץ. פועלים בו כ-30 שחקנים פעילים ועוד כ-70 עובדים. התיאטרון מפעיל גם פרויקטים חינוכיים עבור אוכלוסיות מיוחדות בקהילה, חוגי תיאטרון וסדנאות, במטרה להעצמה עצמית וקבוצתית דרך פעילות בתיאטרון.
הגבעה הקפיטולינית
תיאטרון באר-שבע
תיאטרון צוותא
אבי תקווה
אבי תקווה (נולד ב-28 ביוני 1976) הוא כדורגלן עבר ישראלי אשר שיחק בעמדת הקשר ההתקפי, אחיו הצעיר של כדורגלן העבר שלום תקווה.
קריירה.
תקווה התחיל את הקריירה שלו במחלקת הנוער של מכבי נתניה, עמה זכה בשלוש אליפויות נוער. לאחר מכן שיחק גם במדי הקבוצה הבוגרת של המועדון, אך שותף רק בשישה משחקים. על אף הופעותיו הבודדות סירבו מנהלי המועדון לשחרר את תקווה לקבוצה אחרת, ולבסוף הוא החליט לממש את זכותו ל"הסגר קטין" - לפיו הוא מגיש בקשה להתאחדות לכדורגל, אשר בסיום העונה תכפה ההעברה למועדון הקולט בסיום העונה.
בעקבות בקשתו עבר תקווה בסיום העונה לשחק במדי הפועל כפר סבא. בעונה שלאחר מכן חזר לנתניה, ששיחקה בליגה הארצית (הליגה השנייה דאז). בעונת 1996/1997 שיחק בבני יהודה תל אביב, ובסופה עבר לשחק באירופה, בקבוצה השווייצרית גראסהופרס ציריך. בגארסהופרס שיחק מעונת , בה זכה עמה באליפות, עד לעונת .
לקראת עונת 2000/2001 חזר תקווה לישראל וחתם בהפועל תל אביב, לאחר שהקבוצה זכתה בדאבל בעונה הקודמת וחיפשה מחליף לאחיו, שלום תקווה, שפרש בתום העונה והפך לעוזר המאמן בקבוצה. למרות קרבתו המשפחתית לעוזר המאמן, במהלך העונה הסתכסך אבי תקווה עם המאמן דרור קשטן, ובסיומה של העונה המאכזבת מבחינתו חזר לשווייץ וחתם ביאנג בויז ברן.
לאחר שנתיים בברן חזר תקווה לישראל לקראת עונת 2003/2004 וחתם במכבי פתח תקווה, עמה זכה בגביע הטוטו באותה עונה. הוא המשיך בקבוצה גם בעונת 2004/2005 אך שוחרר לקראת סיום העונה, ב-9 באפריל, אז עבר לשחק תחת הדרכתו של אלי גוטמן בקבוצת פראלימני הקפריסאית.
בעונת 2005/2006 חתם תקווה בהפועל כפר סבא, שהייתה מועמדת ודאית לירידה מליגת העל לליגה הלאומית, אך תחת המאמן אלי אוחנה הצליחה הקבוצה לחולל מהפך ולהנצל מירידה. יכולתו הטובה של תקווה, שתרמה למהפך, לא נעלמה מעיניהם של סקאוטים ומאמנים. במהלך העונה קיבל הצעות מקבוצות בכירות בשווייץ, כמו פ.צ. ציריך ולוזאן, כמו גם מקבוצות מהליגה השווייצרית השנייה. ב-16 במאי 2006 פורסם כי הוא חתם בקבוצת לוגאנו מהליגה השנייה בשווייץ. אולם כשעסקת לוגאנו כבר הייתה סגורה, ותקווה שוחרר מהפועל כפר סבא, הוא החליט במהלך מפתיע לוותר על החוזה עם לוגאנו ובמקומה סיכם לעונה אחת עם קבוצת הכח עמידר רמת גן, עמה ירד בעונה זו לליגה הלאומית. בתום העונה לא הצליח למצוא קבוצה חדשה, ובסופו של דבר פרש ממשחק פעיל.