נשים לב שבבעיה המקורית, אם כל סכום אפשרי של מספרים יכול להיכתב באמצעות P ביטים, אם נפתור את הבעיה המקורית באלגוריתם הקירוב עם formula_49, נפתור את הבעיה בדיוק. לכן אלגוריתם זה הוא פתרון מדויק של הבעיה כשהוא רץ בזמן פולינומי ב-formula_3 וב-formula_51 (כלומר, אקספוננציאלי ב-formula_52).
האלגוריתם המקורב לבעיה הוא:
initialize a list S to contain one element 0.
for each i from 1 to n do
let T be a list consisting of xi + y, for all y in S
let U be the union of T and S
sort U
make S empty
let y be the smallest element of U
add y to S
for each element z of U in increasing order do
//trim the list by eliminating numbers close to one another
//and throw out elements greater than s
if y + cs/n &lt; z ≤ s, set y = z and add z to S
if S contains a number between (1 − c)s and s, output yes, otherwise no
האלגוריתם רץ בזמן פולינומי כיוון שהרשימות S,T,U תמיד בגודל פולינומי ב-n וב-formula_48, ולכן גם כל הפעולות שנעשות עליהן מתבצעות בזמן פולינומי. גודל הרשימות אכן נשאר פולינומי היות שאנו מוסיפים עצמים ל-S אם הם גדולים מהעצם הקודם ב-formula_54 וקטנים מ-formula_55. הצעד שמוודא שההפרש בין כל שני עצמים שמתווספים הוא לפחות formula_54 מוודא שברשימה יש לכל היותר formula_57 עצמים.
האלגוריתם נכון כיוון שבכל צעד מתווספת שגיאה של לכל היותר formula_54, ובמהלך formula_3 שלבים מתווספת שגיאה של לכל היותר formula_60.
Der Jüdische Wecker
במדעי המחשב, RP (ראשי תיבות של Randomized Polynomial time) היא מחלקת הסיבוכיות של כל הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי ביחס לגודל הקלט באופן הבא:
במילים אחרות, האלגוריתם יכול להטיל מטבע בעת ריצתו. המקרה היחידי שבו האלגוריתם מחזיר "כן" הוא אם התשובה היא באמת "כן". לכן, אם האלגוריתם מסיים ועונה "כן", אז התשובה היא בהכרח "כן". עם זאת, האלגוריתם עלול להשיב "לא" וזו תהיה תשובה שגויה.
יש המכנים את המחלקה "R", אך שם זה שגור יותר עבור שפות רקורסיביות.
אם התשובה הנכונה היא "כן" והאלגוריתם מורץ formula_1 פעמים, כאשר תוצאת כל ריצה היא בלתי תלויה סטטיסטית באחרות, הוא יחזיר "כן" לפחות פעם אחת בהסתברות של לפחות formula_2. אז אם האלגוריתם מורץ 100 פעמים, ההסתברות שיענה תשובה שגויה נמוכה יותר מההסתברות שקרניים קוסמיות ישבשו את זיכרון המחשב שמריץ את האלגוריתם. מבחינה זו, אם מקור למספרים רנדומליים זמין, רוב האלגוריתמים הרצים במחלקת RP הם מאוד פרקטיים.
מחלקת הסיבוכיות המשלימה ל-RP קרויה co-RP, והיא כוללת את השפות שעבורן יש אלגוריתם המקבל קלטים בשפה בהסתברות 1, ודוחה בהסתברות הגדולה מ-1/2. גם RP וגם המשלימה co-RP מוכלות במחלקת הסיבוכיות BPP - אשר גם הבעיות במחלקה הזאת נחשבות פתירות ואלגוריתמיהן נחשבים לפרקטיים, הכוללת את כל הבעיות הניתנות להכרעה הסתברותית עם שגיאה דו-צדדית.
אחת השאלות המפורסמות והפתוחות במדעי המחשב נוגעת לדי-רנדומיזציה של אלגוריתמים הסתברותיים עם שגיאה חסומה, כלומר, האם P=RP - ההנחה המקובלת היא שאכן מתקיים השוויון (בניגוד להנחה המקובלת שP וNP לא שווים)
דפרגליים
שנג'ואו 5
שנג'ואו 5 (בסינית מפושטת: 神舟五号) הייתה החללית הסינית המאוישת הראשונה בחלל.
החללית שוגרה ב-15 באוקטובר 2003 כשעליה הטייקונאוט אלוף-משנה יאנג ליוואי. היא המריאה אל שמיים נקיים בדיוק בשעה תשע בבוקר, לפי שעון בייג'ינג ויצאה לדרכה כמתוכנן ממתקן השיגור שבמדבר גובי בצפון מערב סין.
לפי הודעת הממשלה, החללית נכנסה למסלולה 10 דקות מאוחר יותר. למחרת, בשעה 6:04 בבוקר נפתח המצנח של החללית והיא נחתה בשלום בערבות מונגוליה הפנימית, בתום 14 הקפות של כדור הארץ ובכך הייתה הרפובליקה העממית של סין למדינה השלישית בעולם שהצליחה לשגר אדם לחלל בכוחות עצמה.
הכרונולוגיה הסינית
PP (מחלקת סיבוכיות)
במדעי המחשב ובתורת הסיבוכיות, PP, (ראשי תיבות של Probabilistic Polynomial Time), היא מחלקת הסיבוכיות של הבעיות הניתנות להכרעה הסתברותית בזמן פולינומי כאשר האלגוריתם מחזיר תשובה נכונה בהסתברות שגדולה ממש מ-1/2. באופן פורמלי, שפה formula_1 שייכת ל־PP אם קיימת מכונת טיורינג הסתברותית כך שעבור כל מילת קלט formula_2, המכונה רצה זמן פולינומי, ומחזירה פלט (ACCEPT/REJECT) כך שמתקיים
formula_3
formula_4
PP מכילה את RP ,BPP ,Co-RP וגם את NP (ראו פירוט למטה).
המחלקה הוגדרה לראשונה על ידי ג'ון גיל ב-1975
תכונות.
בניגוד למחלקות RP ,BPP ,Co-RP לגביהן ידוע כי ניתן לבצע הגברה, כלומר להקטין את השגיאה עד כדי הסתברות מעריכית בפולינום, לא ידועה תוצאה מסוג זה ב-PP. טכניקת ההגברה של BPP, שהיא הרצות חוזרות של האלגוריתם הבסיסי ובחירת החלטה על פי הרוב, הייתה מובילה למספר לא פולינומי של חזרות ולכן אינה מתאימה לכך.
PP סגור למשלים, חיתוך ואיחוד. אפשר לראות מההגדרה ש- PP סגור למשלים כי אפשר להפוך את התשובה של מכונת טיורנג A. דויד רוסו הראה ב-1985 כי PP סגורה להפרש סימטרי. השאלה אם PP סגורה לאיחוד וחיתוך הייתה שאלה פתוחה במשך 14 שנים עד שזו נפתרה על ידי ביגל, ריינגולד וספילמן. הוכחות חלופיות ניתנו על ידי לי וסקוט ארונסון (הוא הראה כי PostBQP=PP ואז הראה הוכחה פשוטה כי PostBQP סגור לאיחוד וחיתוך).
קשר עם מחלקות אחרות.
ידוע כי BPP מוכלת ב- PP וזאת מההגדרה, ומכאן ברור גם כי P גם כן שייכת למחלקה PP. אפשר להוכיח כי NP מוכלת ב-PP על ידי כך שמראים כי SAT שייכת ל-PP: אפשר לבנות מכונת טיורינג הסתברותית שתעשה זאת על ידי בחירה אקראית של השמה; אם הנוסחה מסופקת המכונה מקבלת ואם לא היא דוחה בהסתברות formula_5. מאחר ש-PP סגורה למשלים אז גם co-NP שייכת ל-PP. אפשר להראות תוצאה חזקה יותר, MA שייכת ל- PP. המחלקה MA היא מחלקת כל השפות שיש להן פרוטוקול מרלין-ארתור וזה נובע ישירות מההגדרה.
עובדה מפתיעה יותר היא שאפשר להראות כי המחלקה BQP מוכלת ב-PP, כאשר BQP היא מחלקת השפות שאפשר לקבל אותן על ידי מכונת טיורינג קוונטית. בנוסף מתקיים formula_6 כלומר PQB נמוכה (Low) ל- PP.
כדי להבין את הכוח של המחלקה PP חוקרים לעיתים את המחלקה formula_7, כלומר P מצוידת עם אורקל של PP. ידוע כי formula_8 כש-P# היא מחלקת הסיבוכיות המכילה את אוסף בעיות הספירה הקשורות לבעיות ההכרעה השייכות למחלקה NP. אחד המשפטים החשובים ביותר בסיבוכיות הוא משפט טודה שמראה כי ניתן לעשות רדוקציה פולינומית דטרמיניסטית מההיררכיה הפולינומית PH ל-PP, כלומר formula_9.
אריק אלנדר (Allender) הראה כי TC0 ⊂ PP, כלומר TC0, מחלקת השפות הניתנות לזיהוי על ידי מעגלים בוליאניים בעומק קבוע וגודל פולינומי המכילים שערי סף עם מספר לא חסום של קלטים, היא תת-קבוצה ממש של PP. ברור כי PP מוכלת ב-EXP אבל אפשר לחזק זאת ל-PSPACE על ידי כך שמראים כי הבעיה MAJSAT שהיא בעיה שלמה למחלקה PP שייכת ל-PSPACE.
אפשר להראות תוצאה דומה למשפט קאנאן (Kannan) למחלקה PP כלומר: (k, ∃ L⊆{0,1}* : L∈PP ∧ L∉SIZE(n^k ∀. טענה זו שונה מהטענה formula_10 כי לכל k אנו מניחים שיש שפה כזו אבל לא לכל k יש שפה אחת משותפת, כלומר עבור k-ים שונים השפות יכולות להיות שונות.
ב-2005 הראה ארונסון כי PostBQP (הרחבה של המחלקה BQP כך שאפשר לעשות התניה על הופעת קיוביטים) שווה ל-PP ובנוסף PP שווה למחלקה PQP שהיא הרחבה של BQP כך שהטעות לא מוגבלת.
לחץ אטמוספרי
גארינצ'ה
מנואל פרנסיסקו דוס סאנטוס (בפורטוגזית: Manuel Francisco dos Santos; 28 באוקטובר 1933 – 20 בינואר 1983), הידוע בכינוי גארינצ'ה (זו ההגייה שהשתרשה בישראל, אך ההגייה הנכונה היא גארינשה; בפורטוגזית: Garrincha), היה כדורגלן ברזילאי ששיחק עם נבחרת ברזיל בקבוצות המנצחות של מונדיאל 1958 ומונדיאל 1962. הוא נחשב לאחד השחקנים הטובים ביותר בהיסטוריה, וזכור בעיקר בזכות יכולות הכדרור שלו.
ילדות.
גארינצ'ה נולד ב-28 באוקטובר 1933 בפאו גרנדה, מחוז מאגה, בריו דה ז'ניירו שבברזיל. רגלו הימנית הייתה נמוכה ב-6 סנטימטר מהשמאלית שלו ודבר זה הוביל לכך שרופא אישר כי הוא ילד נכה. אביו היה אלכוהוליסט, בעיה שגם גארינצ'ה ירש בשלב מאוחר יותר בחייו. בגלל שהיה בעל מבנה גוף קטן הוא נקרא בשם גארינצ'ה על שם ציפור שיר, שם שנשאר מגיל 4 בקרב משפחתו וחבריו.
למרות כי היה מוכר בקרב צופי הכדורגל והיה בעל כישרון עצום הוא שיחק ברמה מקצועית רק בשנות העשרה המאוחרות שלו. אחיו הצעיר, ג'ימי דוס סנטוס, היה גם כן כדורגלן ששיחק 20 פעמים עבור ואסקו דה גאמה בליגה הראשונה ב-1959.
קריירה.
קריירת מועדונים.
ברמת המועדונים, גארינצ'ה שיחק 581 משחקים וכבש 232 שערים בבוטפוגו. הוא שיחק גם בקורינתיאנס, פלמנגו, אולריה בברזיל ואתלטיקו ג'וניור בקולומביה. הקריירה המקצוענית שלו נמשכה מ-1953 עד 1972.
קריירה לאומית.
גארינצ'ה ערך במדי נבחרת ברזיל 50 הופעות בהם כבש 12 שערים בין השנים 1955–1966. הוא הפסיד עימה רק משחק אחד בזמן זה, נגד הונגריה במונדיאל 1966, שהייתה גם להופעתו האחרונה שהוא בסגל שלה. גארינצ'ה לא שיחק במשחק זה ובכך ברזיל לעולם לא הפסידה משחק בו הוא ופלה עלו ביחד בהרכב. הוא ערך את הופעת הבכורה שלו נגד צ'ילה בריו דה ז'ניירו ב-1955. בשתי המהדורות של הקופה אמריקה ב-1957 ו-1959 סיימה ברזיל במקום השני.