השאלה האם P=NP היא בעיה פתוחה מרכזית במדעי המחשב, העוסקת ביכולת לפתור אוסף גדול של בעיות בצורה יעילה. במילים פשוטות, השאלה היא האם כל בעיה שניתן לבדוק עבורה בצורה יעילה האם פתרון מוצע הוא נכון, היא גם בעיה שניתן למצוא עבורה פתרון בצורה יעילה. לפתרון הבעיה ישנן השלכות תאורטיות ומעשיות רבות, והיא זכתה להכרה כאחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה.
היסטוריה.
בשנת 1955 שלח ג'ון נאש מכתב ל-NSA בו הוא ציין כי הוא חושד שבכדי לפרוץ קוד מסובך מספיק זמן ריצה אקספוננציאלי ביחס לאורך המפתח. בשנת 1956, שאל במכתב בינו ובין ג'ון פון נוימן, קורט גדל האם ניתן להוכיח הוכחות מתמטיות בזמן ליניארי או ריבועי וכתוצאה מכך יהיה אפשר להפוך הוכחות לדבר אוטומטי. התכתבויות אלו הופיעו לפני 1971 בו הביאו ההגדרות הפורמליות למושגי P ו-NP ולבעיית P=NP על ידי סטיבן קוק במאמרו "The complexity of theorem proving procedures". בשנת 2000 נבחרה הבעיה להיות אחת מתוך 7 בעיות המילניום של מכון קליי, ואדם אשר פותר אותה יקבל פרס של מיליון דולרים אמריקאים ממכון זה.
המחלקות P ו-NP.
במדעי המחשב מוצעות מספר שיטות למדוד יעילות של אלגוריתם על בסיס הקלט שלו. הגישה הנפוצה היא למדוד את זמן הריצה של האלגוריתם. על מנת למדוד את זמן הריצה בלי תלות במימוש האלגוריתם במחשב זה או אחר, נהוג למדוד את זמן הריצה על פי כמות הצעדים הבסיסיים שהאלגוריתם מבצע (ההגדרה המדויקת של "צעד בסיסי" מבוססת על מכונת טיורינג).
מכיוון שקלטים גדולים יותר לבעיה גוררים לרוב זמן פתרון גדול יותר, זמן הריצה של האלגוריתם נמדד ביחס לאורך בקלט, לכמות הקלט או למורכבותו. אם ניתן לחסום את קצב גדילה של זמן הריצה של האלגוריתם עם גדילת הקלט על ידי פולינום, אומרים כי האלגוריתם פותר את הבעיה בזמן ריצה פולינומי. על פי רוב, זמן ריצה פולינומי נחשב לזמן ריצה סביר לצורך מימוש ביישומים מעשיים (ואף יותר מכך - זמן ריצה שאינו פולינומי נחשב לזמן ריצה שאינו סביר).
לקבוצה P (מלשון Polynomial) שייכת כל בעיית הכרעה שעבורה קיים אלגוריתם המוצא פתרון בזמן ריצה פולינומי.
לקבוצה NP (מלשון Nondeterministic Polynomial) שייכת כל בעיית הכרעה שעבורה קיים אלגוריתם הבודק בזמן ריצה פולינומי האם פתרון מוצע לבעיה אכן פותר אותה. אלגוריתם זה לא בהכרח מסוגל למצוא פתרון, אלא רק לוודא שפתרון מוצע הוא אכן נכון.
ניתן להגדיר את NP בצורה שקולה באמצעות שימוש במושג האי-דטרמיניזם: בעיה שייכת ל-NP אם קיים אלגוריתם אי-דטרמיניסטי הפותר אותן בזמן פולינומי (דהיינו, מצליח למצוא פתרון). באופן ציורי, ניתן לומר כי נותנים לאלגוריתם "להטיל מטבע" בכל שלב של ריצתו על מנת להחליט כיצד להמשיך הלאה, ואותו מטבע תמיד נופל בצורה שמבטיחה שאם יש פתרון, האלגוריתם יצליח למצוא אותו.
בניגוד למה שחלק חושבים, כאשר אומרים שאלגוריתם שייך למחלקה P, זה לא אומר כי זמן הריצה שלו הוא מהר או שבעיה שפתרונה שייך למחלקה זו אומר כי "קל" לפתור אותה, אלא זה פשוט אומר כי זמן הריצה שלה הוא פולינומי, שזה ביחס לזמני ריצה הרבה יותר גדולים כמו אקספוננט, יותר מהיר.
אם כן, בעיית P=NP שואלת האם קל למצוא את הפתרונות של בעיה חישובית שקל לבדוק את הפתרונות שלה. התשובה לכך אינה ידועה, אך ההשערה הרווחת היא ש- P ≠ NP, כלומר, קיימות בעיות שקל לבדוק וקשה לפתור.
חשיבותה הגדולה של המחלקה NP ושל השאלה P=NP נעוצה בעובדה שבעיות נפוצות רבות נמצאות ב-NP, ופעמים רבות הן אף NP-שלמות. עם זאת, לא ידוע עבורן כל אלגוריתם יעיל, וההשערה הרווחת היא שאף לא ייתכנו עבורן אלגוריתמים יעילים, ולכן P ≠ NP.
דוגמה.
בהינתן קבוצה של מספרים שלמים, נדרש לקבוע האם ניתן לחלקה לשתי קבוצות של מספרים כך שסכומן זהה (בעיה זו נקראת בעיית החלוקה, Partition Problem). לדוגמה, הקבוצה {1, 3, 4, 5, 8, 11} ניתנת לחלוקה לשתי קבוצות: הקבוצה {11, 5} והקבוצה {1, 3, 4, 8}, שסכום כל אחת מהן הוא 16. מאידך, הקבוצה {1, 3, 5, 6} לא ניתנת לחלוקה כזו.
ניתן להשתכנע בקלות כי בעיה זו ניתנת לבדיקה באופן יעיל, ולכן נמצאת ב-NP. בהינתן פתרון מוצע - חלוקה של שתי קבוצות - כל שנדרש הוא לחבר את המספרים בכל אחת משתי הקבוצות, ולבדוק האם סכומן זהה.
עם זאת, כלל לא ברור כי בהינתן קבוצה של מספרים, ניתן למצוא באופן יעיל חלוקה לשתי קבוצות שסכומן זהה. יותר סביר להניח, ואכן זוהי ההשערה הרווחת, כי כל אלגוריתם עלול להזדקק למספר גדול יותר של צעדים (למשל: לעבור על חלק גדול מהחלוקות האפשריות, שמספרן תלוי אקספוננציאלית במספר האיברים בקבוצה).
ההיררכיה הפולינומית.
לאור הדעה הרווחת כי NP מכילה ממש את P, ומשום הקושי הרב שחווים בהוכחת (או הפרכת) הטענה, המחקר בסיבוכיות עוסק בעיקר בווריאציות שונות של הבעיה. אחת הווריאציות המוכרות והבסיסיות ביותר היא ההיררכיה הפולינומית (מסומנת PH).
הגדרת המחלקה NP בעזרת מכונות טיורינג שאינה דטרמיניסטית אינה הגדרה יחידה, וניתן להגדיר את המחלקה על ידי שימוש בכמתים לוגיים. את המחלקה NP נגדיר באמצעות הכמת "קיים פתרון" או "קיים פתרון מתקבל". את המחלקה המשלימה co-NP נגדיר באמצעות הכמת "לא קיים פתרון", או באופן קנוני יותר, "כל פתרון אפשרי אינו מתקבל". מכאן ההרחבה להיררכיה הפולינומית טריוויאלית במונחי כמתים - נוסיף שרשראות של כמתים, כלומר, במקום "קיים" (formula_1) או "לכל" (formula_2), נגדיר שרשראות של כמתים, לדוגמה formula_3. כמובן שאין טעם בלשים כמתים מאותו סוג בצמידות.
הגדרת ההיררכיה מתקבלת ישירות מההגדרה על פי כמתים - בדרגה ה-i בהיררכיה, תופענה מחלקות הסיבוכיות עם i כמתים. נשים לב שיש בדיוק 2 מחלקות בכל דרגה, המסומנות formula_4. ההיררכיה נקראת פולינומית מכיוון שכל אחד מהערכים הקשורים (כלומר, הערכים הנמצאים בצמידות לכמת) מוגבלים להיות באורך פולינומי באורך הקלט. ההיררכיה נקראת היררכיה מכיוון שכל המחלקות בדרגה ה-formula_5 מוכלות במחלקה שבדרגה ה-i. נשים לב, שבהצגה זו SAT היא באופן טריוויאלי שפה NP-שלמה.
הקרסת ההיררכיה היא הוכחה שעבור דרגה מסוימת בהיררכיה, מתקיים formula_6, אזי formula_7. משפט זה שימושי מסיבות רבות. באופן מופשט - אם נוכיח שההיררכיה אינה קורסת תחת דרגה מסוימת, אזי formula_8.
משפט הקרסת ההיררכיה שימושי באופן נוסף - מספיק להוכיח ש-formula_9, והתוצאה המיידית היא ש-P שונה מ-NP.
דים סאם
דים סאם (בסינית: 点心, פין-יין: Diǎnxīn, יוטפנג: dim² sam¹, מילולית: נגיעות קטנות בלב) הוא שמם הקנטונזי של מגוון רחב של מאכלים סיניים המאופיינים בכך שהם מוגשים במנות קטנות לצד תה, חלקן מאודות בכלי ייעודי וחלקן מטוגנות או מוקפצות. את הדים סאם נהוג לרוב להגיש בארוחת יָם–צַ'ה (סינית: 饮茶, יוטפנג: jam2 caa4, מילולית מקנטונזית: "לשתות תה"), הדומה לארוחת בוהריים או ארוחת מנחה ומקורה בגואנגדונג. מסעדות דים סאם לעיתים מוגדרות כבית תה, ומקורן, כמו מקור רוב המנות המוגשות בהן, במחוז גואנגדונג שבסין, אך כיום נפוצות בכל רחבי המדינה ומדינות נוספות בהם יש אוכלוסייה סינית גדולה.
אופן ההגשה.
במסעדות דים סאם נהוגה שיטת הגשה לפיה המלצר עובר עם עגלה עמוסה כלי אידוי ובהן מנות שונות, הסועד בוחר את המנות אותן הוא רוצה והמלצר ממשיך הלאה. בתום הארוחה משלם הסועד לפי כמות כלי האידוי על שולחנו. מסעדות דים סאם במערב בדרך כלל מגישות רק את הכיסונים והלחמניות ולא את שאר המנות.
היסטוריה.
מסעדות הדים סאם החלו כבתי תה ששכנו לאורך דרך המשי. במאה העשירית לספירה עיר הנמל הדרומית גואנגג'ואו ראתה גדילה פתאומית מספר המבקרים בקרבה, ובעיקרם סוחרים ופרנסים. בתקופה זו בתי התה החלו להגיש שתי מנות אוכל קטנות ומעוצבות בקפידה לצד התה, בדומה לטאפס הספרדי. במאה השלוש עשרה, עם פלישת המונגולים לסין, החצר הקיסרית הדרימה למחוז גואנגדונג כדי להתרחק מהחזית. שם האליטה הפוליטית של סין נחשפה למנהגי המזון המקומיים והפיצו אותם ברחבי סין.
הקטורת
קרייזלר
קבוצת קרייזלר (באנגלית: FCA US LLC) היא חברה אמריקנית לייצור כלי רכב. היא נוסדה ב-1925 על ידי וולטר קרייזלר, מחלוצי תעשיית הרכב בארצות הברית. בשנת 1928 נבנה עבור משרדי החברה בניו יורק הבניין הגבוה ביותר בעולם דאז, אשר נקרא בניין קרייזלר. כיום בניינה של חברת קרייזלר ממוקם בשיקגו שבארצות הברית.
בשנת 2009 פתחה החברה בהליכי ארגון מחדש באמצעות חוקי פשיטת הרגל בארצות הברית. במסגרת ההליכים נרכשו בהדרגה מניות החברה על ידי יצרן הרכב האיטלקי פיאט. בשנת 2014 השלימה פיאט את רכישת החברה והוקמה החברה פיאט-קרייזלר. בשנת 2021 התמזגה פיאט-קרייזלר עם קבוצת PSA הצרפתית והמותג קרייזלר הפך לחלק מהתאגיד סטלנטיס שמרכזה בהולנד.
היסטוריה.
חטיבת דה סוטו של חברת קרייזלר עסקה בייצור ובשיווק רכב אמריקאי משנת 1928–1968. חטיבת דה סוטו בנתה יותר מ-2 מיליון כלי רכב מאז שנת 1928.
חטיבת המכוניות דה סוטו קרויה על שם ארננדו דה סוטו, מגלה הארצות הספרדי שהוביל את המסע האירופי הראשון לשטח עליו משתרעת כיום ארצות הברית, היה האירופי הראשון שגילה את נהר המיסיסיפי.
לקראת סוף שנות ה-70 של המאה ה-20 נכנסה החברה לקשיים ועמדה על סף הליך פירוק. אנשי החברה פנו ללי איאקוקה שהועזב מתפקיד נשיא חטיבת הרכב של פורד והוא על ידי בקשת ערבויות מהממשל האמריקאי (מעשה תקדימי באותה עת) ועל ידי פיתוח מכוניות לקהלים ספציפיים הצליח להציל את החברה ולהפוך אותה שוב למצליחה.