לודוויג שמר על יחסים טובים עם בית הבסבורג, ובשנת 1352 סייע לאלברכט השני, דוכס אוסטריה נגד הקונפדרציה השווייצרית. בשנת 1359 השיא לודוויג את בנו מיינהארד השלישי, רוזן גוריציה-טירול למרגרטה מאוסטריה, בתו של אלברכט השני, דוכס אוסטריה, ומשום כך ביטלו בני בית הבסבורג את הנידוי שהוטל עליו ועל אשתו.
ב-18 בספטמבר 1361 מת לודוויג, ובנו מיינהארד השלישי, רוזן גוריציה-טירול ירש את נחלותיו. כעבור שנתיים מת מיינהארד ללא יורשים, ובעקבות כך ירש שטפן השני, דוכס בוואריה את בוואריה העליונה, ואילו רודולף הרביעי, דוכס אוסטריה ירש את רוזנות טירול.
משפחתו.
בשנת 1324 התחתן לודוויג עם מרגרט מדנמרק, בתם של כריסטופר השני, מלך דנמרק ואופמיה מפומרניה, אולם לא היו לו ילדים ממנה.
ב-10 בפברואר 1342 התחתן לודוויג עם מרגרטה, רוזנת טירול, בתם של היינריך, מלך בוהמיה ואדליידה מבראונשווייג, ממנה היו לו 4 ילדים:
טבח ג'אליאנוואלה באג
חשופים בצריח (ספר)
Live from Paris
Live from Paris (בספרדית: En Vivo Desde París) הוא אלבום ההופעה הרביעי של הזמרת-יוצרת הקולומביאנית שאקירה. האלבום מאגד כמה וכמה הופעות של הזמרת שהתקיימו בעיר פריז, שבצרפת. האלבום זכה במהרה להצלחה רבה ברחבי העולם כאשר מכר למעלה מ-90,000 עותקים במקסיקו, ולמעלה מ-100,000 עותקים בצרפת. ה-DVD שיצא לאלבום זכה להצלחה פחותה כאשר מכר 15,000 עותקים בצרפת ו-5,000 עותקים בפולין.
במצעדים האלבום זכה להצלחה בינונית כאשר הצליח להגיע למקום ה-1 במצעד אלבומי הפופ הלטיניים שבארצות הברית, ובמצעדים אחרים הצליח האלבום להגיע לחמישיות והעשיריות הפותחות במדינות רבות.
האלבום מחולק לשני חלקים, חלק של DVD, וחלק של האלבום עצמו, החלק של ה-DVD זכה להצלחה פחותה משל האלבום אך הצליח למכור כמויות נאות של עותקים ביחס לגרסה הרגילה של האלבום.
רקע.
לאחר סיבוב ההופעות המצליח והגדול של הזמרת הנקרא "The Sun Comes Out World Tour", אשר קידם את האלבומים "Sale el Sol" ו-"She Wolf" הודיעה הזמרת כי עתיד לצאת אלבום הופעה חדש אשר יאגד הופעות שנערכו בפריז שבצרפת. האלבום יצא לאור ב-2 בדצמבר 2011, כמה חודשים לאחר סיום סיבוב ההופעות וצאת שני האלבומים.
לודוויג השלישי, דוכס בוואריה
לודוויג השלישי, דוכס בוואריה (בגרמנית: Ludwig III. von Bayern; 9 בפברואר 1269–13 במאי 1296), היה דוכס בוואריה התחתונה ממות אביו ב- 1290 ועד למותו.
ביוגרפיה.
לודוויג נולד ב-9 בפברואר 1269 בלנדסהוט, להיינריך השלושה עשר, דוכס בוואריה ואליזבת מהונגריה, דוכסית בוואריה, בתם של בלה הרביעי, מלך הונגריה ומריה לסקרינה. בשנת 1287 התחתן לודוויג עם איזבל מלורן, בתו של פרידריך השלישי, דוכס לורן, אך לא היו לו ילדים ממנה.
בשנת 1290 מת אביו היינריך השלושה עשר, דוכס בוואריה, ולודוויג ואחיו אוטו השלישי, דוכס בוואריה ושטפן הראשון, דוכס בוואריה ירשו את נחלותיו. לודוויג התנהג בחצרו בפזרנות, ובשל כך העלה את המיסים על מנת לכסות את הוצאותיו. ב-13 במאי 1296 מת לודוויג השלישי, ואחיו קיבלו את נחלתו.
אפסילון בברבור
ε בברבור (נקרא לפעמים גם גִ'ייֶנָה או גליזה 806.1, וכן LHS 5358) הוא כוכב בקבוצת הכוכבים ברבור, שבהירות נראיתו היא השלישית בעוצמתה בקבוצה. הכוכב מייצג את הכנף המזרחית של הברבור וזהו גם מקור שמו, ג'יינה, שהוא שיבוש של המילה הערבית جناح - ג'וּנה - כנף. השם ג'יינה ניתן גם לכוכב γ בעורב המייצג את הכנף של העורב, כך שלפעמים הכוכב נקרא גם גִ'ייֶנָה סִיגְנִי שמשלב את המילה (המשובשת) "כנף" בערבית עם "של הברבור" בלטינית. (הכוכב γ בעורב נקרא לפעמים באופן דומה "גִ'ייֶנָה קוֹרְבִי").
תכונות.
ε בברבור נמצא במרחק של כ-73 שנות אור ממערכת השמש ובהירות נראיתו היא מדרגה 2.48. זהו ענק כתום מסוג ספקטרלי K0 III, מסתו מעט פחות משתי מסות שמש, רדיוסו קצת יותר מפי 10 מרדיוס השמש, טמפרטורת פניו כ-4,730 קלווין והוא מאיר בעוצמה של פי 45 מעוצמת ההארה של השמש באור נראה, ובערך פי 60 בצירוף הקרינה בתחום התת-אדום. ל-ε בברבור יש תנועה עצמית גדולה למדי של קרוב לחצי שניית קשת בשנה ובשל כך הוא נכלל בקטלוג לויטן לכוכבים בעלי תנועה עצמית גדולה. בשל קרבתו למערכת השמש הוא נכלל גם בקטלוג גליזה לכוכבים קרובים.
כוכבים נלווים.
במרחק זוויתי של כ-55 שניות קשת מ-ε בברבור יש כוכב עם בהירות מדרגה 12, שסומן בעבר כ-ε בברבור B, אך ככל הנראה הוא רחוק בהרבה ונמצא רק במקרה על אותו קו ראייה, שכן לשניים יש מהירות רדיאלית ותנועה עצמית שונות והמרחק הזוויתי ביניהם הולך וגדל. לעומת זה, במרחק של כ-78 שניות קשת יש כוכב נוסף, שמסומן כ-ε בברבור C, שנע באותו הכיוון ואותה המהירות כמו הכוכב הראשי, כך שככל הנראה הם קשורים זה לזה. ε בברבור C הוא ננס אדום מסוג ספקטרלי M4 עם בהירות מדרגה 13.4, ובהנחה שהם אכן קשורים זה לזה, הוא מקיף את הכוכב הראשי במרחק של לפחות 1,700 יחידות אסטרונומיות (פי 40 מהמרחק של פלוטו מהשמש) ובזמן הקפה של לפחות 50,000 שנים.
בעבר נטען ש-ε בברבור עצמו הוא כוכב כפול ספקטרוסקופי, אך מדידות עדכניות לא הצליחו לאשר או לשלול את קיומו של בן זוג קרוב.
גליזה 806.1
LHS 5358
בתורת הסיבוכיות, השפה TQBF (קיצור ל-True quantified boolean formulas; או: QBF, QSAT) היא שפה פורמלית במחלקה PSPACE. השפה TQBF היא השפה של כל הנוסחות הבוליאניות עם כמתים שמוערכות לאמת. ניתן לראות את TQBF כהכללה ל-SAT. השפה ידועה בהיותה שפה PSPACE-Complete, כלומר לכל שפה ב-PSPACE קיימת רדוקציה פולינומית ל-TQBF.
בניגוד ל-SAT בה השאלה היא האם קיימת הצבת אמת, ב-TQBF לכל נוסחה יש ערך אמת או שקר יחיד, מכיוון שאין משתנים חופשיים.
הסבר - נוסחת SAT נראית כך:
formula_1
ועבור ההצבה formula_2 הנוסחה מקבלת ערך אמת בעוד עבור formula_3 הנוסחה מקבלת ערך שקר.
הנוסחה השקולה ב-QBF נראית כך:
formula_4
וערכה הוא אמת, מכיוון שקיימים formula_5 עבורם יש הצבות אמת.
ניתן לחשוב על TQBF כעל משחק בין שני שחקנים, המשחקים בתורות. משתנים המופיעים בנוסחה עם כמת "קיים" תואמים לקיום מהלך עבור שחקן בתור כלשהו, ומשתנים המופיעים בנוסחה עם כמת "לכל" תואמים לכך שתוצאת המשחק אינה תלויה במהלך ששחקן מבצע (כלומר, כל מהלך יכול להוביל לניצחון). נוסחת TQBF שהכמת הראשון בה הוא "קיים" תואמת לנוסחת משחק בה לשחקן הראשון אסטרטגיה מנצחת (כיוון שקיים מהלך של השחקן עבורו לכל מהלך אחר של היריב, השחקן ינצח).
סקירה.
בתורת הסיבוכיות, השפה QBF היא הכללה של השפה SAT בה לכל משתנה מוצמד כמת. מכיוון ש-QBF נמצאת ב-PSPACE, אין חובה לכתוב את הנוסחאות בצורת CNF מכיוון שזה ודאי לא הופך את השפה ל"קלה" יותר, אך גם לא הופך אותה לקשה יותר. מאחר שלכל משתנה מוצמד כמת, לנוסחה יש ערך אמת או שקר, והשפה QBF היא של הנוסחאות שמקבלות ערך אמת. פורמלית : formula_6
דוגמה:
מתקיים formula_8.
QBF היא בעיה שלמה של המחלקה PSPACE, המחלקה של הבעיות הניתנות לפתרון על ידי מכונת טיורינג דטרמיניסטית או לא דטרמיניסטית בסיבוכיות מקום פולינומית וזמן שאינו מוגבל. נוסחה ב-QBF ניתנת לפתרון טריוויאלי המשתמש בסיבוכיות מקום ליניארית וסיבוכיות זמן אקספוננציאלית.
ההוכחה לתוצאה המפתיעה IP = PSPACE נעשתה על ידי הצגת הוכחה אינטראקטיבית ל-QBF.
ל-QBF מספר צורות נורמליות. אחת הצורות החשובות היא הצורה הנורמלית של פרנקס אם היא מהצורה
הצורה הזאת חשובה במיוחד בגלל הקשר שלה להיררכיה הפולינומית. כידוע,
וגם המחלקה formula_11 מוגדרת כל השפות A עבורן קיים מוודא פולינומי formula_12 ופולינום formula_13 כך ש-
והנוסחה למעלה ניתנת לרדוקציה טריוויאלית ל-QBF.
PH ו-PSPACE.
ההנחה הרווחת כיום היא ש formula_15, מכיוון שאם PH=PSPACE, אזי QBF נמצא באחת מדרגות ההיררכיה הפולינומית ולכן ההיררכיה קורסת בדרגה זאת, אף על פי שמקובל להניח שזה לא קורה.
פתירת QBF.
ל-QBF פתרון טריוויאלי בסיבוכיות מקום ליניארית.
אלגוריתם לפתרון:
ניתוח סיבוכיות מקום:
הפונקציה המתארת את סיבוכיות המקום של האלגוריתם היא formula_22, מכיוון שבזמן הקריאה הרקורסיבית, אנחנו שומרים כמות זיכרון קבועה.
סיבוכיות הזמן היא אקספוננציאלית
שלמות של QBF.
נרצה להראות שהשפה QBF שלמה ב-PSPACE תחת רדוקציית קארפ פולינומית, כלומר
formula_23
או, בכתיב חסכני, formula_24
לשם כך נגדיר ראשית את גרף הקונפיגורציות formula_25 של מכונת טיורינג M:
גרף הקונפיגורציות של מכונת טיורינג M הוא גרף אשר כל קודקוד בו הוא קונפיגורציה של המכונה, ובין קודקוד לקודקוד יש קשת אם ורק אם ניתן להגיע מקונפיגורציה אחת לשנייה.
קונפיגורציה של מכונת טיורינג היא המצב הנוכחי של המכונה, דהיינו
נשים לב, שמכיוון שהמכונה שלנו פולינומית במקום, קונפיגורציה בודדת שלה היא גם פולינומית במקום.
קל לראות שאם קלט x נמצא בשפה אזי קיים מסלול בין המצב ההתחלתי שלו formula_26 למצב המקבל שלו formula_27.
נגדיר פונקציה formula_28, אשר מחזירה אמת אם ורק אם קיים מסלול בין C ל-C' בגרף.
ניסיון: נגדיר את הנוסחה באופן הבא:
formula_29-C'
הנוסחה הנ"ל באורך אקספוננציאלי. נגדיר פונקציה חדשה: formula_30 הוא אמת אם ורק קיים מסלול בין C ל-C' באורך לכל היותר formula_31.
נשים לב שמתקיים: formula_32
משמעות הנוסחה למעלה: קיים מסלול בין formula_33 ל-formula_34 אם ורק אם קיימת קונפיגורציה formula_35 כך שיש מסלול בין formula_33 ל-formula_35 ובין formula_35 ל-formula_34.
הנוסחה עדיין אקספוננציאלית. נקצר אותה עם הכמת לכל.
formula_40