tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
חידוש מסוים נגזר מכך והאופן שבו המכונית בורחת בהתקף לאחר שתיית חומר תרופתי.
הציור מוגדר היטב, צילום ברור והקלטה סבירה".
ב-10 במאי 1931, עיתון חדשות הקולנוע "The Film Daily" פרסם: "מצחיק.
בעיית התחבורה מטופלת היטב על ידי מיקי בהפצה ההומוריסטית הזו.
וולט דיסני אסף המון בדיחות חדשות וחדשניות שמעוררות צחוק באופן וודאי.
מיקי מתחיל בתור נהג מונית אבל מתקשה בנסיעה עם חזיר גדול כלקוח.
האקשן הוא מהיר והסנכרון והאפקטים עשויים היטב".
במדעי המחשב, בעיית אריזה בדליים (bin packing) היא בעיית אופטימיזציה חשובה, בה יש לארוז חפצים במספר מינימלי של דליים.
נתונים חפצים, לכל אחד מהם נפח: .
בנוסף נתונים מספר לא מוגבל של דליים, שכל אחד מהם בנפח ומתקיים לכל i (אחרת אי אפשר לארוז אותם בשום דרך).
יש לארוז את החפצים במספר מינימלי של דליים, כך שבכל דלי הנפח הכולל של החפצים לא יעלה על נפח הדלי.
באופן פורמלי, יש לחלק את המספרים למספר מינימלי של קבוצות זרות, שסכום כל קבוצה לא יעלה על .
הבעיה היא NP-קשה, והצגתה כבעיית הכרעה: "האם ניתן לארוז בפחות מ-k דליים?" היא NP-שלמה.
הבעיה היא גם NP קשה חזקה, כלומר גם קבלת הקלט בכתיב אונארי היא NP קשה (בניגוד לבעיית תרמיל הגב למשל).
יתרה מכך, בהנחה ש-P שונה מ-NP, אין גם אלגוריתם קירוב ביחס יותר טוב מ 1.5. ניתן לראות זאת על ידי רדוקציה מבעיית החלוקה: בהינתן וקטור , נקח ואז בעיית האריזה בדליים תתן פתרון עם שני דליים אם ורק אם בעיית החלוקה פתירה, אחרת 3 דליים ומעלה.
ניתן לפתור את הבעיה באמצעות תכנון ליניארי בשלמים.
המשתנים הם שמציין "הפריט ה-i נכנס לדלי ה-j" וכן שמציין "הדלי ה-j נמצא בשימוש" (צריך רק n משתנים כאלה, כי תמיד אפשר לפתור ב-n דליים - להכניס כל פריט לדלי אחר).
לכל i (הפריט נכנס לבדיוק דלי 1) ובנוסף אילוצים שכופים על כל המשתנים להיות בינאריים.
פונקציית המטרה היא למזער את .
אלגוריתם חמדן לבעיה יהיה: לעבור על הפריטים אחד אחד, ובכל פעם לנסות להכניס אותו לאחד הדליים הקיימים.
אם לא מצליחים, לפתוח דלי חדש ולשים רק אותו.
מימוש האלגוריתם מושפע מהסדר בו עוברים על הפריטים, ומהסדר בו עוברים על הדליים כשמנסים למצוא דלי פנוי.
בעיית האופק או בעיית ההומוגניות של היקום היא בעיה פתוחה בפיזיקה התיאורתית, המצביעה על בעייתיות במודל התרחבות היקום המוקדם (המפץ הגדול) הקלאסי.
צבירי גלקסיות הצד אחד של השמיים נראים זהה כמעט לחלוטין לצבירי גלקסיות בצד השני של השמיים.
אם תאורית המפץ הגדול נכונה, כלומר אם אכן היקום התחיל בנקודה בה כל החומר והאנרגיה, וכן מרחב הזמן היו מרוכזים בנקודה קטנה בצורה אינסופית ומשם המרחב זמן התחיל להתרחב, הרי שלא היה זמן לשני חלקיקי אור (פוטונים) להעביר מידע בין שני צדי היקום התינוק.
לחלקיקים לא היה מספיק זמן להערבב ולהחליף ביניהם פוטונים וירטואליים בשביל לתאם טמפרטורה, כי גם אם היקום המוקדם מאוד היה בגודל שרירותי 1, מהירות האור (המהירות הגבוהה ביותר האפשרית) לא הייתה מהירה מספיק בשביל להגיע מקצה אחד של היקום לקצה השני שלו לפני התרחבות היקום.
הצעות נוספות שהוצעו לפתרון בעיית האופק הן תאורית היקומים המקבילים (תאוריה המציעה כי יש אינסוף יקומים, ולכן העובדה שאנחנו מוצאים את עצמנו ביקום הומוגני היא בעלת פתרון סטטיסטי).
תאוריות נוספות שהוצעו לפתרון הבעיה הן המיתר הקוסמי, כלומר חור תולעת שנוצר עקב שזירה קוונטית בין שני חלקיקים ביקום המוקדם, שבעקבות התנפחות היקום מאפשר להעביר מידע מיד (מהר יותר ממהירות האור), וכן הסברים קוונטים אחרים כגון היקום בעל האלקטרון האחד וכדומה.
נכון ל-2024, התאוריה המקובלת בקרב קהילת המחקר היא תאורית האינפלציה, שמסבירה גם בעיות נוספות במודל המפץ הגדול הקלאסי.
בעיטה היא פעולה בסיסית בכדורגל שבה משתמשים השחקנים כדי להזיז את הכדור על המגרש.
בעיטות מבוצעות באמצעות הרגליים והן חלק מרכזי בטקטיקה, בהתקפה ובהגנה של המשחק.
תרגול ושיפור יכולות הבעיטה הם מהמרכיבים החשובים ביותר באימוני כדורגל, והם נלמדים החל מגיל צעיר ועד לרמות המקצועיות הגבוהות ביותר.
בכדורגל המודרני יש דגש רב על פיתוח יכולות בעיטה, במיוחד אצל שחקני התקפה.
שחקנים כמו ליונל מסי ודייוויד בקהאם נודעים בזכות היכולת שלהם להבקיע מבעיטות חופשיות.
כיום נעשה שימוש בטכנולוגיות מתקדמות כמו GPS ומצלמות חכמות כדי לנתח את ביצועי הבעיטות של השחקנים.
נתונים אלו כוללים את מהירות הכדור, זווית הבעיטה ומיקום הפגיעה בכדור.
מידע זה משמש את המאמנים כדי לשפר את טכניקות הבעיטה של השחקנים ולהתאים את האימונים בהתאם.
בעיטת פנים הרגל נחשבת לטכניקה היסודית ביותר.
היא מבוצעת באמצעות החלק הפנימי של כף הרגל, ומשמשת לרוב למסירות מדויקות במרחקים קצרים ובינוניים.
בשל שטח המגע הרחב, בעיטה זו מקנה לשחקן שליטה טובה יותר על הכדור ויכולת גבוהה לשמור על דיוק.
בעיטה חזקה, המכונה גם "בעיטת חיצון" או "בעיטת שפיץ", מתבצעת בעזרת קדמת כף הרגל.
הבעיטה פופולרית מאוד בבעיטות לכיוון השער, כיוון שהיא מייצרת עוצמה רבה.
בעיטות אלו מגיעות למהירויות גבוהות, ולעיתים עוברות את ה-100 קמ"ש.
בעיטת עוצמה מתבצעת בדרך כלל כאשר השחקן מנסה להבקיע מרחוק או להרחיק את הכדור מאזור מסוכן.
בעיטת צ'יפ היא טכניקה עדינה יותר, בה השחקן מכה בכדור בחלקו התחתון ומרים אותו מעל השחקן היריב או השוער.
בעיטות צ'יפ מתבצעות בעיקר במצבים בהם השוער יצא מהשער והשחקן מנצל את המצב להבקיע בכדור מדויק.
בעיטת עקב מבוצעת באמצעות החלק האחורי של כף הרגל.
היא משמשת לעיתים קרובות במסירות מפתיעות כאשר השחקן עם גבו לשער או לשחקן אחר.
זוהי טכניקה מורכבת הדורשת תזמון טוב ודיוק, והיא נפוצה פחות מהבעיטות המסורתיות, אך מהווה כלי חשוב במצבים בלתי צפויים במשחק.
בעיטת מסובבת (או "בעיטת הבננה") היא בעיטה בה השחקן גורם לכדור לשנות את כיוון מעופו במהלך המסלול.
הבעיטה מבוצעת בדרך כלל באמצעות קדמת כף הרגל בצידו של הכדור, דבר אשר גורם לו להסתובב סביב צירו.
הבעיטה מתבצעת לרוב בבעיטות קרן ובבעיטות חופשיות.
אחת הבעיטות המסובבות הידועות בכדורגל המודרני היא זאת של רוברטו קרלוס שהבקיע בבעיטה חופשית ממרחק של יותר מ-35 מטר.
בעיטת מספרת היא אחת מהבעיטות המרהיבות ביותר בכדורגל.
היא מתבצעת כאשר השחקן מזנק לאוויר, מבצע סלטה לאחור ובועט בכדור תוך כדי נפילה.
בעיטה זו דורשת גמישות, כוח וביטחון, והיא בדרך כלל נחשבת למהלך אקרובטי מורכב.
מספר שחקנים, כמו כריסטיאנו רונאלדו וזלאטן איברהימוביץ', התפרסמו בזכות ביצועים יוצאי דופן של בעיטות מספרת.
כדי לבצע בעיטה מוצלחת, על השחקן להתחשב במספר גורמים:
נקודת המגע עם הכדור: הפגיעה בכדור בנקודות שונות תשפיע על מסלולו.
בעיטה בחלק התחתון של הכדור תרים אותו באוויר, בעוד שבעיטה בחלקו העליון תגרום לכדור לנוע בצורה שטוחה.
בעיטה בצד הכדור תגרום לכדור לנוע על צירו, מה שיכול לגרום לבעיטת מסובבת.
גובה הכדור: גובה הכדור משפיע על מהירותו.
כדור גבוה מהיר יותר בשל אי חיכוכו בקרקע, דבר אשר מאט את מהירות הכדור.
רגל התמיכה: רגל התמיכה היא הרגל הלא בועטת, והיא ממוקמת לצד הכדור בעת הבעיטה.
מיקום נכון של רגל זו מקנה יציבות ומשפר את הדיוק.
במדע הטילאות, בעיית גודארד עוסקת באופטימיזציה של הגובה אליו מגיעה רקטה, הנוסקת אנכית, בהתחשב בגרר האטמוספירי ובכוח הכבידה.
ביותר דיוק, הבעיה מבקשת לדעת מהו פרופיל הדחף של המנוע הרקטי (הפונקציה המתארת את הדחף שהמנוע מפיק בתלות בזמן) הדרוש כדי להביא אותה לגובה המרבי האפשרי עבור כמות דלק נתונה.
הבעיה הוצעה לראשונה על ידי רוברט גודארד בפרסומו "שיטה להגעה לגבהים קיצוניים" מ-1919.
הכוחות הפועלים על רקטה (הנוסקת אנכית) במעופה הם הדחף הרקטי שמפיק המנוע, כוח הכבידה (משקלה העצמי של הרקטה) וכוח התנגדות האוויר.
על מנת שהרקטה תוכל בכלל להמריא, הדחף ההתחלתי המינימלי צריך להיות גדול ממשקלה העצמי.
במילים אחרות, אלמלא היה פועל גרר על הרקטה (אם לא הייתה אטמוספירה), שיקול זה היה מביא מיידית למסקנה שהדחף צריך להיות המקסימלי האפשרי במשך כל שלב ההאצה.
אולם הגרר האטמוספירי, שיחסי הן למהירות הרקטה והן לצפיפות האוויר המקומית, משתנה משמעותית במהלך נסיקת הרקטה.
מכיוון שצפיפות האוויר יורדת מעריכית עם הגובה, הגיוני יותר להביא את הרקטה למהירות גבוהה דווקא היכן שצפיפות האוויר נמוכה יותר, כך שהתנגדות האוויר תגרע פחות מהגובה המרבי אליו תגיע.
כלומר, בניגוד לשיקול הראשון, שיקול זה מביא למסקנה שכדאי יותר להתחיל עם דחף נמוך (כאשר צפיפות האוויר גבוהה), ולהגביר אותו ככל שצפיפות האוויר יורדת – זאת על מנת שהרקטה לא תנוע במהירות גבוהה היכן שצפיפות האוויר גבוהה.
התחשבות דקדקנית בפרטי הגרר האטמוספירי למציאת פרופיל הדחף האופטימלי מצריכה כלים מתמטיים מיוחדים מתחום חשבון הווריאציות, וזאת משום שגרר אטמוספירי אינו כוח משמר (כמו כל כוחות החיכוך) ולכן אין זה אפשרי לתאר את מצבה האנרגטי של הרקטה על ידי פונקציית מצב שמשתניה הטבעיים הם גובהה, מהירותה וכמות הדלק שנותרה לה.
כמות האנרגיה שהרקטה איבדה עקב הגרר תלויה בהיסטוריה המדויקת של מעופה האנכי, ולכן משוואת אוילר-לגראנז' אינה מועילה כאן.
מורכבות נוספת נובעת מירידת המסה של הרקטה עם הזמן, עובדה שמרמזת שכדאי לנצל את הדחף כאשר מסתה נמוכה יותר על מנת להשיג שינויי מהירות משמעותיים יותר.
עם זאת, בפועל קיים גרר וגם שלב ההאצה לא בהכרח זניח באורכו מזמן המעוף - אדרבא, כפי שהוסבר בפסקה הקודמת, אופטימיזציה של הגובה דווקא מצריכה ניצול של ההאצה בגובה רב כאשר התנגדות האוויר נמוכה.
פרופיל הדחף האופטימלי נגזר מן האיזון שבין שיקולים מנוגדים אלו.
במתמטיקה ובמדעי המחשב, בעיית הכרעה היא בעיה אשר יש לה תשובה של "כן" או "לא".
דוגמה: השאלה האם מספר טבעי נתון הוא ראשוני היא בעיית הכרעה.
מאידך, הבעיה "מציאת המספר הראשוני הקטן ביותר בעל 77 ספרות" אינה בעיית הכרעה, שכן התשובה עבורה אינה "כן" או "לא".
בעיית הכרעה ידועה בתולדות המתמטיקה היא הבעיה העשירית של הילברט.
בעיות הכרעה שקולות לשפות פורמליות, כך שמילה נתונה נמצאת בשפה אם ורק אם התשובה עבורה בבעיית ההכרעה היא "כן".
קבוצות מסוימות של בעיות הכרעה, כגון זו הקרויה NP-קשה, הן נושא מרכזי במדעי המחשב, בהיותן בגדר בעיה פתוחה רחבת היקף.
תורת החישוביות היא תחום יסודי במדעי המחשב החוקר את היכולות והמגבלות של כל המחשבים באשר הם.
שאלה מרכזית בתורת החישוביות היא האם כל בעיית הכרעה ניתנת לפתרון על ידי תוכנית מחשב כלשהי.
בהסתמך על משפט קנטור ניתן להראות שהתשובה שלילית.
כל קלט (סופי) אפשרי הנתון בשפה כלשהי ניתן לקודד (לייצג) כמספר טבעי.
קידוד שכזה נקרא מספור גדל ומחשבים מודרניים מיישמים אותו על ידי קידוד בינארי.
בהינתן קידוד שכזה, לכל בעיית הכרעה ניתן להגדיר את הקבוצה הכוללת את כל המספרים הטבעיים שמקודדים קלטים שלגביהם התשובה לבעיה היא "כן".
ולהפך, לכל קבוצה של מספרים טבעיים ניתן להגדיר בעיית הכרעה שמשיבה "כן" על כל הקלטים המקודדים על ידי מספר טבעי שנמצא ב-.
במילים אחרות, את קבוצת כל בעיות ההכרעה ניתן לזהות עם קבוצת כל התת-קבוצות של הטבעיים, .
מצד שני, כל תוכנית מחשב היא רצף סופי של סימנים של שפת תכנות.
לכן כל תוכנית מחשב ניתן לקודד כמספר טבעי יחיד (ואכן בפועל כל תוכנית מחשב בשפה מסוימת מתרגמת לקידוד בינארי שונה בשפת מכונה).
מכאן שקבוצת כל תוכניות המחשב שקולה לקבוצת המספרים הטבעיים .
משפט קנטור קובע שעוצמת (שהיא עוצמת הרצף) גדולה מעוצמת (שהיא אָלֶף אֶפֶס), ולכן יש "הרבה יותר" בעיות הכרעה מאשר תוכניות מחשב אפשריות (על אף שמן השניים יש אינסוף).
מכאן שישנן בעיות הכרעה (ולמעשה, כמעט כל בעיות ההכרעה) שאינן ניתנות לפתרון על ידי אף תוכנית מחשב.
הדוגמה המוכרת ביותר לבעיית הכרעה שאין תוכנית הפותרת אותה היא בעיית העצירה.
אלן טיורינג הוכיח זאת בשנת 1936 בשיטת הלכסון.
דוגמאות רבות נוספות מגיעות ממשפט רייס.
חלק ניכר מתורת הסיבוכיות עוסק בבעיות הכרעה.
העניין בבעיות הכרעה נובע מכך שהטיפול המתמטי בהן הוא פשוט, שכן התשובה לבעיה מוגבלת ל-"כן" ו-"לא".
עם זאת, בעיות שאינן בעיות הכרעה ניתנות להמרה לבעיות הכרעה שקולות.
דוגמה לכך היא הבעיה "האם יש גורם ראשוני": כאשר נתונים שני מספרים שלמים, n ו-k, ענה האם ל-n יש גורם ראשוני קטן מ-k.
אם אנו מסוגלים לפתור את בעיית ההכרעה הזו באמצעות משאבים בסדר גודל מסוים, אנו יכולים לפתור את הבעיה "פירוק לגורמים", שאינה בעיית הכרעה, באמצעות משאבים מאותו סדר גודל, וזאת על ידי סדרה של שאלות התוחמות את ערכו האפשרי של k.
בעיית הסוכן הנוסע היא בעיה ידועה בתורת הגרפים ובתורת הסיבוכיות, המעלה את השאלה הבאה: "בהינתן רשימת ערים והמרחק בין כל שתי ערים, מהו המסלול הקצר ביותר, אשר יעבור בכל עיר פעם אחת, ויחזור לעיר ממנה התחיל?"
הבעיה נכללת במחלקת הסיבוכיות NP-קשיות, והיא אחת מהבעיות המרכזיות בתחום האופטימיזציה.
מדריך לסוכן הנוסע משנת 1832 מזכיר את הבעיה ומכיל דוגמאות למסלולים בגרמניה ושווייץ, אבל לא מכיל התייחסות מתמטית לנושא.
בעיית הסוכן הנוסע נוסחה לראשונה במאה ה-19 על ידי המתמטיקאי האירי ויליאם רואן המילטון והמתמטיקאי הבריטי תומאס קירקמן .
המילטון פיתח בשנת 1857 את "משחק איקוסיאן" שמטרתו הייתה למצוא מסלול המילטוני שיעבור בכל הקודקודים של דודקהדרון בדיוק פעם אחת ויחזור לנקודת ההתחלה.
בשנות ה-60 התפתחה גישה חדשה – במקום לחפש את הפתרון האופטימלי, החלו אנשים לחפש את הפתרון הגרוע ביותר ובכך למצוא חסם עליון לבעיה.
בעשורים שלאחר מכן נחקרה הבעיה על ידי מתמטיקאים, חוקרי מדעי המחשב, פיזיקאים ומדענים אחרים.
בשנת 1972 ריצ'רד קארפ הראה שמסלול המילטון היא בעיה השייכת לקטגוריה NP-שלמה, ובכך סיפק הסבר מתמטי לקושי החישובי במציאת מסלול אופטימלי.
בשנת 1991 פרסם ג'רארד ריינלט ספרייה בשם TSPLIB שכללה אוסף של רשימות ערים לדוגמה בדרגות קושי שונות.
חוקרים רבים עשו שימוש נרחב בספרייה, ובשנת 2006 ויליאם ג'ון קוק וחוקרים נוספים חישבו מסלול אופטימלי שעבר ב-85,900 נקודות, נכון להיום החישוב הגדול ביותר מתוך TSPLIB.
ספריה זו מתוחזקת לצורך בדיקת אלגוריתמים לפתרון הבעיה.
ניתן להציג את בעיית הסוכן הנוסע כגרף ממושקל לא מכוון, בו כל עיר היא צומת, דרך בין עיר לעיר היא קשת, והמרחק בין כל שתי ערים מצוין על ידי משקל הקשת המחברת ביניהן.
בצורה כזו ניתן לשאול מהו המסלול עם המשקל הנמוך ביותר, שיצא ויחזור לאותו צומת לאחר שעבר בכל צומת אחר פעם אחת בדיוק.
לרוב הבעיה תוצג על גבי גרף שלם (גרף בו כל זוג צמתים מחוברים בקשת).
אם לא קיימת דרך בין שתי ערים ניתן להוסיף לגרף קשת עם משקל גבוה מאוד ובכך להשלים את הגרף לגרף שלם מבלי לפגוע בפתרון האופטימלי.
בגרסה הסימטרית של הבעיה, המרחק בין כל שתי ערים זהה למרחק בכיוון ההפוך בין אותן שתי ערים.
במקרה כזה תוצג הבעיה כגרף לא מכוון.
סימטריה זו מקטינה את מספר הפתרונות האפשריים פי שניים.
בגרסה הא-סימטרית של הבעיה, ייתכן ודרך לא תתאפשר לשני הכיוונים, או שהמרחק בכיוונים שונים יהיה שונה.
במקרה כזה תוצג הבעיה כגרף מכוון.
דוגמאות לדרכים בהן ניתן להפוך את הבעיה לבעיה א-סימטרית הן כבישים חד סטריים, נתיבי תעופה בין ערים עם זמני הגעה או עלויות שונות, תאונות דרכים ועוד.
בעיה זו נכללת בקטגוריה NP-קשה, והצגתה כבעיית הכרעה (בהינתן האורך X, קבע האם קיים מסלול שאורכו קטן מ-X) שייכת לקטגוריה NP-שלמה.
לכן, אם מניחים ש-P שונה מ-NP, זמן הריצה הגרוע ביותר של כל אלגוריתם לפתרון הבעיה יהיה יותר מפולינומי כתלות בקלט (מספר הערים).
ניסוח הבעיה במונחי תורת הגרפים: בהינתן גרף ממושקל שלם לא מכוון, מהו המסלול ההמילטוני שמשקלו הוא הקטן ביותר.
הדרישה שהמסלול יסתיים בנקודה בה התחיל לא משפיעה על סיבוכיות החישוב של הבעיה.
בעיית הסוכן הנוסע היא מקרה פרטי של בעיית הקונה הנוסע העוסקת בקונה שעליו לקנות מספר פריטים.
הוא יכול לרכוש אותם בערים שונות אך לא בכולן אותם המחירים.
המטרה היא למצוא את המסלול שיקטין את עלויות הרכישה (מחיר הפריטים ומחיר הנסיעה) למינימום.
הקווים המנחים לטיפול בבעיות NP-קשות הם:
תכנון אלגוריתמים למציאת פתרון מדויק (יעבדו בזמן סביר רק עבור מספר קטן של ערים)
תכנון אלגוריתמים היוריסטים למציאת קירובים טובים לפתרון, אך לא פתרונות מדויקים מוכחים.
מציאת מקרים פרטיים של הבעיה להם קיימים פתרונות מדויקים.
פתרון פשוט לבעיה הוא בדיקת כל התמורות האפשריות וחיפוש המסלול הקצר ביותר (תוך שימוש בכוח גס).
פתרון זה מצריך בדיקה של אפשרויות (עצרת של מספר הערים), ולכן סיבוכיות זמן הריצה במקרה כזה תהיה .
חישוב כזה הופך מהר מאוד לבלתי מעשי (לבלתי יעיל, במינוח של מדעי המחשב).
דוגמה להמחשת הבעיה: אם ישנן 70 ערים בהן על הסוכן לבקר, יצטרך הסוכן לבחון מסלולי נסיעה אפשריים, אשר מהווים מספר רב יותר ממספר האטומים ביקום כולו.
בשנת 2001 נמצא פתרון מדויק של הבעיה עם 15,112 ערים בגרמניה מתוך TSPLIB.
החישובים התבצעו ברשת של 110 מעבדים באוניברסיטאות רייס ופרינסטון שבארצות הברית.
במאי 2004 נמצא מסלול באורך 72,500 קילומטרים שעבר בכל 24,978 הערים בשוודיה והוכח כמסלול הקצר ביותר שקיים.
במרץ 2005 נמצא מסלול שעבר דרך 33,810 נקודות על מעגל מודפס שאורכו היה 66,048,945 (יחידות TSPLIB).
חישוב המסלול ארך זמן המקביל ל-15.7 שנות חישוב של מעבד ממוצע באותה התקופה.
באפריל 2006 נמצא מסלול שעבר דרך 85,900 נקודות, בכוח עיבוד שהקביל ל-136 שנות חישוב.
אף על פי שהבעיה קשה לחישוב, כיום ידועות מספר היוריסטיקות לפתרונות מקורבים שלה.
שיטות מודרניות יכולות למצוא פתרונות לבעיות גדולות מאוד (מיליוני ערים), בזמן סביר, שמובטחים להיות בסטייה של עד 2%–3% מהמסלול האופטימלי.
דוגמה לאלגוריתם חמדן המחפש קירוב למסלול הקצר ביותר היא "שיטת השכן הקרוב".
בשיטה זו בכל צעד הסוכן יפנה לעיר הקרובה אליו ביותר שעוד לא ביקר בה.
בעזרת אלגוריתם זה ניתן לקבל במהירות מסלול קצר ויעיל.
עבור מספר מסוים של ערים בפיזור אקראי לרוב יתקבל מסלול ארוך ב-25% מהמסלול הקצר ביותר.
עם זאת, קיימים סידורי ערים מיוחדים שגורמים לאלגוריתם זה להניב את התוצאה הגרועה ביותר, הן בגרסה הסימטרית והן בגרסה הא-סימטרית.
בנוסף לחשיבותה התאורטית בתחום חקר ביצועים, לבעיה גם חשיבות מעשית – לא רק בתחום התחבורה והלוגיסטיקה, אלא גם בייצורו של מעגל מודפס, שבו על מכונת הייצור לעבור מסלול מסוים בעת שהיא יוצרת חורים בלוח שעליו נמצא המעגל.
שימוש נוסף מגיע מתחום האסטרונומיה – אסטרונומים הצופים בגופים רבים בחלל רוצים לצמצם את הזמן שנדרש לכיוון הטלסקופ בין גוף לגוף ככל האפשר, ובכך לייעל את עבודתם.
בעיית הסוכן הנוסע עניינה חוקרים מתחום הפסיכולוגיה הקוגניטיבית שבדקו את הביצועים האנושיים בהתמודדות עם הבעיה.
מחקרים מראים שאנשים מסוגלים ליצור פתרונות איכותיים במהירות, מסקנה שרומזת שייתכן וביצועי מחשבים בתחום יכולים להשתפר על ידי הבנה וחיקוי של דרכי חשיבה של בני אדם.
מחקרים אלו גם הובילו לגילויים חדשים על המנגנון שמאחורי המחשבה האנושית.
הגיליון הראשון של כתב העת "Journal of Problem Solving" הוקדש לנושא של ביצועים אנושיים בניסיון פתרון הבעיה.
סרט הקולנוע "הסוכן הנוסע" (Travelling Salesman) מאת הבמאי טימותי לנזון הוא סיפור על ארבעה מתמטיקאים שנשכרו על ידי ממשלת ארצות הברית כדי לפתור את הבעיה הפתוחה במדעי המחשב: שאלת P=NP.
בעיית הגלריה לאמנות היא בעיה תאורטית מפורסמת בתחום הגאומטריה החישובית, העוסקת במבנה של מצולעים מישוריים.
הבעיה, שהוצגה בשנת 1973 על ידי המתמטיקאי ויקטור קלי, מבקשת למצוא את מספר השומרים הקטן ביותר שיוכלו, מבלי לעזוב את משמרתם, להשגיח על כל פינה בגלריה לאמנות, שקירותיה ישרים.
באופן פורמלי, נקודה A "משגיחה" על נקודה B בתוך מצולע, אם הקו הישר המחבר אותן נמצא כולו בתוך המצולע.
בהינתן מצולע חסר חורים, השאלה היא מהו המספר הקטן ביותר של נקודות שכל נקודה במצולע נתונה תחת השגחתה של אחת מהן.
ואצלב כבטל (Václav Chvátal) הראה כי בכל מצולע ללא חורים בעל n קודקודים שומרים מספיקים.
ההוכחה להלן מבוססת על טיעון של סטיבן פיסק.
היא מסתמכת על היכולת למצוא שילוש עבור כל מצולע פשוט.
השיטה היא זו: ראשית מוצאים שילוש למצולע המבוקש.
אחר כך צובעים בשלושה צבעים את הקודקודים של המצולע, כך ששני קודקודים המחוברים בקו לא יהיו בעלי אותו צבע.
ניתן להוכיח כי צביעה שכזו תמיד אפשרית וגם לספק אלגוריתם למציאתה (ההוכחה מבוססת על כך שהגרף הדואלי למצולע המשולש הוא בהכרח עץ, עבור מצולעים ללא חורים).
כעת בוחרים את הצבע שבו נצבע מספר הקודקודים הקטן ביותר וה"שומרים" הם הנקודות שצבועות באותו צבע.
מכיוון שקודקודי כל אחד מהמשולשים בשילוש של המצולע צבועים בכל שלושת הצבעים (כי כל שני קודקודים מחוברים בקו, ולכן אם היו שני קודקודים בעלי אותו צבע, זה היה בסתירה לדרישת הצביעה) הרי שבכל אחד מהמשולשים נמצא שומר.
מכיוון שמשולש הוא צורה קמורה, די בשומר זה כדי לשמור על כל המשולש.
לכן קבוצת השומרים שנבחרה מספיקה כדי לשמור על המצולע כולו.
אם למצולע קודקודים, הרי שמספר הנקודות שנצבעו בצבע שהופיע הכי מעט פעמים לא עולה על .
ניתן להוכיח כי זהו חסם עליון למספר השומרים, דהיינו קיימים מצולעים שבהם נדרש כמספר הזה של שומרים.
הבעיה של מציאת המספר המינימלי של שומרים עבור מצולע מסוים (שיכול להיות קטן בהרבה מ-, למשל, למצולע קמור די בשומר יחיד) היא בעיה NP-קשה.
בעיית המדידה היא אחד הקשיים המושגיים המורכבים ביותר במכניקת הקוונטים.
בעיית המדידה מתארת את הכשל המתקיים בתיאור המתמטי הרציף של מערכת קוונטית כאשר מתבצעים מדידה וכימות של אחד או יותר ממאפייני המערכת.
טרם ביצוע מדידה ניתן לחשב את התנהגות המערכת -למשל, גל אור - על ידי פונקציית הגל שהיא פתרון למשוואת שרדינגר.
אולם מרגע ביצוע מדידה תוצאה זו כבר לא מתאימה למציאות הנצפית.
ניסויים רבים מראים שאין זה משנה כיצד מבוצעת המדידה.
גם במדידה עקיפה, שכביכול לא אמורה להשפיע על התנהגות גל האור, קיימת תופעה זו.
בעיית המדידה אינה נובעת מתמטית ממכניקת הקוונטים.
היא תוצאה של ניסויים, שמדגימים שוב ושוב שהתנהגות כל מערכת משתנה באופן חד ברגע שמתבצעת מדידה.
מערכת פיזיקלית קוונטית מתוארת על ידי פונקציית הגל (או "פונקציית מצב") שלה .
פונקציה זו מגדירה על-פי-רוב את ההסתברות של המערכת להימצא במצב נתון, מבחינה פורמלית על פונקציית הגל לפתור את משוואת שרדינגר.
ניתן כאמור לאפיין מערכת קוונטית בעזרת פונקציית הגל שלה, התפתחות המערכת בזמן, פירושה - תיאור מצבי המערכת המשתנים על פני הזמן: נתאר מערכת הנמצאת בזמן על ידי המצב ובזמן
על ידי המצב כאשר מעבר המערכת בין מצביה השונים בזמן משמעותו שקיים אופרטור U כך שמתקיים
מבחינה מתמטית האופרטור האוניטרי U מעביר את המערכת בין מצביה המשתנים על פני הזמן.
האופרטור U המאפשר הצגת מעברי המערכת המתפתחים עושה מלאכתו נאמנה כל עוד לא ערכנו מדידה על מאפייני המערכת.
הקושי התעורר בעקבות תוצאותיהם של ניסויים פיזיקליים שונים (כמו ניסוי שני הסדקים) שהדגימו מצב מוזר, לפיו עריכת המדידה גורמת לקריסת פונקציית הגל, כלומר: בתיאור המערכת על ידי המצבים כאשר בין הזמנים בוצעה מדידה לא קיים אופרטור U אוניטרי כך ש־ בשונה מהמקרה שלא בוצעה מדידה בין שני הזמנים.
פונקציית הגל מתארת את ההסתברות להימצאות המערכת במצב מוגדר בתוך מרחב המצבים האפשריים מבחינה פיזיקלית, ביצוע המדידה גורם "להכרעה" בין מצבי הסופרפוזיציה הקוונטית של המערכת שמשמעו קריסת פונקציית הגל והיעדר יכולת לבטא מתמטית את מעברי המערכת ממצב שלפני המדידה למצב שאחרי המדידה.
מדידת גודל פיזיקלי היא תהליך פיזיקלי כמו כל תהליך פיזיקלי אחר - משמע, בעיית המדידה היא בעיה חריפה אשר פוגמת בעקביות הפיזיקה כולה ומעוררת שאלות מדעיות ופילוסופיות כאחד.
ליישוב בעיית המדידה, הוצעו הסברים שונים ופרשנויות שונות.
בין הפרשנויות והניסיונות הידועים ביותר לפתרון בעיה זו נמנה פירוש העולמות המרובים של הפיזיקאי יו אברט.
על פי פירוש זה פונקציית הגל היא פונקציה "עולמית", הכוללת את המערכת הפיזיקלית, הצופה, התקני המדידה וכך הלאה.
עם ביצוע המדידה עוברת פונקציית הגל המוכללת טרנספורמציה רציפה ואינה קורסת, ומשמעות הדבר שמרחב המצבים מכיל כעת כמה עולמות אשר בכל אחד מהם יש מידע שונה על אותה מדידה עצמה.
למרות היותו של פתרון זה עקבי מבחינה מתמטית הוא נדחה על ידי מרבית הפיזיקאים.
בעיית המדידה מופיעה רק בעצמים קוונטים כגון חלקיקים קטנים ואינה נראית בעצמים "גדולים מספיק" כגון אבן או כיסא, שמתנהגים בהתאם לחוקי הפיזיקה הקלאסית.
השאלה באיזה גודל המערכת יוצאת מהתחום הקוונטי לתחום הקלאסי היא מקרה של פרדוקס הערימה שעדיין לא נמצא לו פתרון משביע רצון.
הפיזיקאי נילס בוהר הציע את המושג "נס המערכת" על מנת להסביר שעבור מערכת גדולה מספיק האפקטים הקוונטים מבטלים אחד את השני ונשארים עם פיזיקה קלאסית, תשובתו הייתה עמומה ולא סיפקה קריטריון לקביעה מתי מערכת גדולה מספיק ומתי מתרחש המעבר.
בשנים האחרונות מתנהל מחקר בתחום שבין פיזיקה מאקרוסקופית (עצמים קלאסיים) לפיזיקה מיקרוסקופית (עצמים קוונטים).
פיזיקה זו - הנקראת פיזיקה מזוסקופית - אמורה לחקור שאלה זו ובאמצעות ניסויים בננוטכנולוגיה לבדוק אפקטים קוונטים במערכות שגודלן ככמה עשרות מולקולות.
בעיית המסה החסרה היא אחת הבעיות הפתוחות המרכזיות באסטרופיזיקה המודרנית.
לפי חוק הכבידה של ניוטון מושפע מסלולו של עצם בחלל בעיקר מכח המשיכה של עצמים סמוכים לו.
עוצמת כח המשיכה תלויה במרחקו ובמסתו של העצם המושך.
כך למשל, תנועתן של גלקסיות בצביר תלויה במסתן של הגלקסיות האחרות בצביר.
בגלקסיות ספירליות נעים רוב הכוכבים במסלול מעגלי סביב מרכז הגלקסיה.
אפשר לחשב את מהירותו של כוכב בשולי הגלקסיה מתוך מסתה המשוערת.
ככל שהגלקסיה כבדה יותר, כך ינועו בה הכוכבים מהר יותר.
החומר המאיר בגלקסיה, שבו אפשר לצפות ישירות, הוא כוכבים, ענני גז ואבק בין כוכבי, שאת מסתם ניתן להעריך בשיטות אסטרונומיות מקובלות.
עדויות שהחלו להצטבר בשנות ה-70 של המאה ה-20 מצביעות על כך שאם הערכת מסת הגלקסיה לפי עוצמת ההארה שלה נכונה, אזי מהירותם של ענני מימן בשולי גלקסיות ספירליות רבות, גבוהה בהרבה מהמהירות הצפויה להם על פי חוק הכבידה של ניוטון.
אם מניחים שחוק הכבידה וחוקי התנועה של ניוטון בכל זאת תקפים, מתחייב מכך שעוצמת ההארה של החומר הגלקטי איננה מהווה מדד להערכת המסה הגלקטית.
אי התאמה בין הערכת מסה גלקטית לפי עוצמת ההארה לבין מהירויות של גלקסיות בצבירים זוהתה כבר ב-1933 בתצפיות שערך האסטרופיזיקאי השווייצרי פריץ צוויקי כשהשתמש לצורך חישוביו במשפט הוויראליות.
על-פי ההערכות המקוריות של צוויקי, הגלקסיות שבהן צפה כבדות פי ארבע מאות מן המסה שנצפתה ישירות.
מאז השתכללו הן אמצעי התצפית והמדידה והן המודלים של מבנה הכוכבים, וכיום (2018) ההערכה הרווחת היא שמסת החומר הרגיל מהווה רק כ-4.9% ממסת החומר ביקום, בעוד 95.1% היא מסת חומר אפל או אנרגיה אפלה.
תאוריות אחרות מערערות על התוקף האבסולוטי של חוקי ניוטון.
מכאן נובע שחוק הכבידה של ניוטון איננו תקף כאשר התאוצה הרדיאלית היא בעלת ערכים נמוכים כמו אלה המתקיימים בשולי הגלקסיות הספירליות בהן נצפית התופעה, וחוק אחר המתאים לתצפיות תופס את מקומו.
ניתוח פיזור המסה בגלקסיה אופיינית
חומר הנמצא במרחק r ממרכז הגלקסיה נע במהירות משיקית הקרובה ל- , כאשר היא מסת החומר הגלקטי המרוכזת בתוך הרדיוס r.
בגלקסיה שבה פיזור המסה הוא בעל סימטריה מעגלית צופים חוקי ניוטון שמהירות הסיבוב תלך ותתקרב לאפס כאשר r גדל.
עקומת סיבוב כזאת מתוארת כקו A באיור משמאל.
עקומת המהירות האופיינית לתצפיות בפועל היא העקומה המסומנת B באיור, שעל פיה מהירות הסיבוב מתקרבת לקבוע .
על מנת שהיא תתאים לחוקי ניוטון יש להניח שפיזור המסה בגלקסיה הוא , כלומר, יש יותר מסה הרחק ממרכז הגלקסיה מאשר קרוב למרכז.
מבנה היפותטי זה של פיזור החומר האפל בגלקסיה נקרא הילה.
בעיית המזכירה היא סוגיה מתמטית בתורת ההסתברות שמתארת מצב שבו צריך לבחור בין מספר אפשרויות שמתגלות זו אחר זו.
לאחר שאפשרות מסוימת מתגלה, אפשר לבחור בה או לוותר עליה.
אם בוחרים באפשרות, לא ניתן להחליף אותה באפשרות אחרת שמתגלה מאוחר יותר.
אם מוותרים על האפשרות, לא ניתן לחזור אליה מאוחר יותר.
סיפור שנועד להמחיש בעיה זו, ושעל שמו היא נקראת, מספר על מעסיקה שמחפשת מזכירה ומפרסמת מודעה בעיתון שעליה עונות מועמדות שמגיעות למשרדה.
ברצונה של המעסיקה לשכור את המועמדת הטובה ביותר מבין אלו שהופיעו.
את המועמדות היא מראיינת זו אחר זו בסדר אקראי, ואחרי כל ראיון, עליה להחליט אם להציע למועמדת הנוכחית את המשרה או לעבור למועמדת הבאה.
בעת שהיא מחליטה, היא יכולה לדרג את המועמדות שראתה עד עתה, אך אין ביכולתה להשוות אותן למועמדות שטרם ראיינה.
אם תחליט המעסיקה לא להציע למועמדת הנוכחית את המשרה, היא תעבור לעבוד במקום אחר ולכן לא תסכים לקבל את המשרה אם לאחר שראיינה עוד מועמדות תחזור ותציע לה את המשרה.
לכן, מיד אחרי ראיון שקיימה עם כל מועמדת, חייבת המעסיקה להתחייב להעסיקה או לוותר על שירותיה.
תנאי הבעיה קובעים שאם לא נשכרה אף מועמדת לפני המועמדת האחרונה, המעבידה תהיה חייבת לשכור אותה.
בגרסה אחרת של הבעיה מסופר על רווק שחבריו סידרו לו אוסף מועמדות שיוכל לשאת לאישה, ולכן לפעמים מכנים בעיה זו "בעיית הנישואים" או "בעיית הרווק".
השאלה שהבעיה עוסקת בה היא כיצד אפשר להגדיל את הסיכוי לשכור את המועמדת הטובה ביותר (או להציע נישואין לאישה הטובה ביותר), ומה ההסתברות שהמועמדת הטובה ביותר תיבחר תחת האסטרטגיה האופטימלית.
הפתרון האופטימלי לבעיה מתאפיין בכך שעבור ערכים גדולים של , ההסתברות לבחור במועמדת הטובה ביותר היא קצת יותר משליש, או ליתר דיוק היא קרובה ל- (אחד חלקי הקבוע ℮ ששווה בערך 2.71828).
תוצאה זו נחשבת כמפתיעה, מפני שממבט ראשון קשה להאמין שמתוך 100 מועמדות, ההסתברות שנצליח לבחור את המועמדת הטובה ביותר תהיה כל כך גבוהה, בפרט שבחירה אקראית (למשל, אם תמיד נשכור את המועמדת החמישית שנראיין, תהיה אשר תהיה) תבחר במועמדת הטובה ביותר רק פעם אחת למאה.
בקרב מתמטיקאים, הבעיה הייתה ידועה מתחילת שנות ה-1950, אך הבעיה והפתרון לא נכתבו או פורסמו.
בפעם הראשונה שהבעיה הוזכרה בכתב הייתה בטור של מרטין גרדנר מפברואר 1960 בירחון Scientific American.
כפי שגרדנר ניסח את הבעיה, היא אינה זהה במדויק לבעיית המזכירה, אך הוא התעלם מההבדלים בפתרונו והתייחס אליה כבעיית המזכירה כפי שהיא ידועה כיום .
הפתרון לבעיה פורסם חודש לאחר מכן, ויוחס למתמטיקאים מוזר ופאונדר.
ב-1963 הציבו זוג מתמטיקאים, ב.
ביסינג'ר וקונרד סיגל, את אותה הבעיה בכתב-העת המתמטי
The American Mathematical Monthly כאתגר לפותרים, וכעבור כמה חודשים פורסם הפתרון, עם הערה שגם הבעיה וגם הפתרון כבר פורסמו ב-Scientific American מספר שנים קודם.
ישנן מועמדות למשרה, מספר שידוע מראש.
את המועמדות אפשר לדרג מ-1 עד לפי המוסכמה שדרוג יותר גבוה ניתן למועמדת מועדפת (כלומר המועמדת המועדפת ביותר תדורג כ-).
מכיוון שישנן מועמדות, מספר האפשרויות שאפשר לסדר אותן בתור הוא:
כדוגמה, כש- שווה ל-3, ישנן 6 אפשרויות לסדר את שלוש המועמדות (שמסודרות מימין לשמאל):
ההנחה היא שהסדר בו המועמדות יופיעו נבחר בהתפלגות אחידה מבין כל הדרכים שניתן לסדר אותן.
ההנחה האחרונה שמנחה את הבעיה היא שניתן להשוות את המועמדות שכבר הופיעו ביניהן, אך לא ניתן לדעת איך הן משתוות למועמדות שעוד לא הופיעו.
כלומר, אם ראינו רק חצי מהמועמדות, נוכל לקבוע איזו הטובה ביותר מביניהן, אך לא נדע מאומה איך הטובה ביותר תשתווה למועמדות שתורן עדיין לא הגיע.
כדוגמה, נגיד שישנן 3 מועמדות, ונניח שכבר פגשנו את שתי המועמדות הראשונות אך לא את השלישית, ושהמועמדת הראשונה הייתה עדיפה על השנייה.
מכך אפשר להסיק שסדר העדיפויות של המועמדות (מהעדיפות הנמוכה לעדיפות הגבוהה) חייב להיות אחד משלושת הבאים:
מכיוון שכל סדר מופיע בהסתברות שווה, שלוש האפשרויות סבירות באותה מידה.
לכן, איננו יודעים אם המועמדת הראשונה היא המועמדת הכי טובה מבין השלושה או האם המועמדת השלישית שטרם ראינו עדיפה על שתי קודמותיה.
עם זאת, ניתן להסיק שההסתברות שהמועמדת האחרונה היא הטובה ביותר היא רק 1/3, משום שרק באחת משלוש האפשרויות תהיה מועמדת זו הטובה ביותר, ובאותה מידה ההסתברות שהמועמדת הראשונה היא הטובה ביותר היא 2/3.
השאלה דנה באיך ניתן להגדיל את ההסתברות שנבחר במועמדת העדיפה על כל האחרות, ומהי אותה הסתברות.
ניתן להוכיח שהאסטרטגיה שמבטיחה את ההסתברות הגבוהה ביותר היא לפסוח על מספר קבוע מראש של מועמדות (שתלוי במספר N), ואז לבחור את המועמדת הבאה שתבוא שתהיה מועדפת על פני כל אלה שקדמו לה (אם יש כזו – אחרת נגיע למועמדת האחרונה ולא נותר אלא לשכור אותה).
כאמור, מספר המועמדות עליו כדאי לפסוח תלוי ב-.
אבל אפשר להראות שעבור גדול דיו, מספר המועמדות שעליו כדאי לוותר שואף ל- .
במילים אחרות, עבור מספר גדול של מועמדות, האסטרטגיה האופטימלית היא לפסוח על אחוז קבוע מהמועמדות (בערך 37%) ואז לבחור את המועמדת הראשונה שעדיפה על הטובה מבין המועמדות הראשונות הללו.
כפי שכבר הוזכר לעיל, תחת אסטרטגיה זו, ההסתברות שנבחר נכון היא בערך , קירוב שיהיה יותר מדיוק ככל ש- יותר גדול.
בהינתן שנפסח על מספר מועמדות, הסיבה מדוע כדאי לבחור במועמדת אם ורק אם היא עדיפה על כל אלה שקדמו לה ברור: אם לא ננהג כך, נבחר במודע מועמדת שאינה המועדפת ביותר, כי כבר קיימת מועמדת שראיינו קודם שמועדפת על פניה.
פחות ברור מדוע עדיף לפסוח על מספר קבוע של מועמדות ורק אז לבחור (בלי קשר לדירוג ביניהן).
המקרה שבו שווה ל-3 שופך קצת אור מדוע עדיף לפסוח על מספר מועמדות.
אם נבחר תמיד במועמדת שמקומה בתור קבוע, למשל את הראשונה (או השנייה, או השלישית), ההסתברות שנבחר את המועמדת הטובה ביותר היא שליש.
לעומת זאת, אם תמיד נפסח על הראשונה ונבחר את המועמדת הבאה שעדיפה עליה, ההסתברות שנבחר נכון עולה לחצי.
את זה אפשר לראות על ידי ניתוח של כל האפשרויות בהן יופיעו המועמדות.
במקרים הבאים, שיטה זו תבחר את המועמדת הנכונה:
מדוע האסטרטגיה מצליחה לבחור נכון בהסתברות יותר גבוהה?
מצד אחד, אם המועמדת הטובה ביותר היא הראשונה, אף פעם לא נבחר בה.
לעומת זאת, אם כבר פסחנו על מועמדת ונתעקש לשכור מועמדת רק אם היא יותר טובה מזו שכבר פסחנו עליה, נגדיל את הסיכוי שנבחר בטובה ביותר אם היא תבוא יותר מאוחר בתור.
מכך, היתרון בלפסוח על מספר מועמדות הוא שאם המועמדת הטובה ביותר תבוא יותר מאוחר, נוכל לזהות אותה יותר בקלות בגלל שנוכל להשוות אותה למספר מועמדות שכבר קדמו לה.
כשלראשונה העלה לכתב מרטין גרדנר את הבעיה, לה קרא "משחק גוגול", הוא ניסח אותה באופן קצת שונה מכפי שתוארה לעיל (וביסינג'ר וסיגל ניסחו את הבעיה באותה צורה כמוהו כשהציגו אותה ב-American Mathematical Monthly).
ההבדל מצביע על החשיבות בניסוח בעיה כזו באופן מדויק.
בפרט, גרדנר תיאר מצב בו אדם כותב מספרים שונים על פיסות נייר, זורק את כולן לכובע, ושולף אותן בסדר אקראי.
הוא שאל כיצד ניתן להגדיל את ההסתברות שנבחר במספר הגבוה ביותר מבין כל הפתקים.
לכאורה, תיאור זה נראה זהה לבעיית המזכירה לעיל.
אך יש הבדל חשוב: בבעיה הזו, ניתן לראות את הערך של המספרים שכתובים על הפתקים.
הבדל זה חשוב, משום שייתכן שנוכל להיעזר בערכי המספרים עצמם לשפר את הסיכויים שנבחר נכון.
זה תלוי באיך בדיוק האדם שרשם את המספרים בחר אותם.
למשל, אם אנחנו יודעים שהוא כתב את המספרים השלמים מ-1 עד N, נוכל בקלות להבטיח שנבחר במספר הגבוה ביותר על ידי זה שנחכה עד המספר N ואז נפסיק.
אם אנחנו יודעים שהאדם בחר את המספרים באופן אקראי ובלתי תלוי מהתפלגות קבועה, עדיין ניתן להשתמש בערכים שנראה לשפר את ההסתברות שנבחר במספר הגבוה ביותר.
למשל, אם נראה מספר גבוה בפתק הראשון, נוכל להסיק שההסתברות שנראה מספר עוד יותר גבוה בעתיד נמוכה אפילו שטרם ראינו את המספרים הבאים.
להבדיל, בבעיית המזכירה ההנחה היא שניתן לדרג רק את המועמדות שהופיעו עד עתה, ואי אפשר לדעת איך הן משתוות למועמדות שעדיין לא ראינו.
בפרט, למועמדת אין ערך כמו בבעיה אותה תיאר גרדנר שבו נוכל אולי להיעזר ולנחש איך היא תשתווה למועמדות שטרם ראינו.
כשגרדנר הציב את הבעיה, הוא התמקד על פתרונות שמתעלמים מהערכים של המספרים עצמם ומתייחסים רק לדירוג ביניהם, ולכן הפתרון שהציב זהה לפתרון בעיית המזכירה.
אך אם לא נציב תנאי זה, הבעיה שהציב גרדנר אינה מוגדרת דיה בלי הסבר מדויק של איך בחר האדם את המספרים אותם הוא טמן בכובע.
מבחינה זו דומה הבעיה לפרדוקס המעטפות, שמקורו נעוץ בכך שהבעיה אינה מוגדרת דיה בלי לנקוב בהתפלגות ממנה נבחרים הערכים במעטפות, ולבעיית מונטי הול, שאף היא אינה מוגדרת דיה בלי תיאור מפורט של איך בוחר המנחה מתי לפתוח דלתות ואיזו דלתות יבחר.
במקרה ש-N שווה ל-2, התשובה היא לא: תמיד נוכל לשפר את הסיכוי לבחור נכון אם נעזר בערכים עצמם.
במקרה ש- גדול מ-2, התשובה אינה ידועה.
אבל, פרגסון הוכיח במאמרו שהפתרון לבעיית המזכירה הוא כמעט אופטימלי, כלומר תמיד אפשר לבחור את המספרים בדרך כזו שההסתברות שנבחר נכון תחת האסטרטגיה האופטימלית עולה על ההסתברות לפי הפתרון שמתעלם מהערכים עצמם ברמה קטנה עד כמה שנדרש.
מתמטיקאים הציעו מספר הכללות של בעיית המזכירה הקלאסית כפי שהוגדרה כאן.
אפשר לחשוב על בעיית המזכירה לעיל כאילו ניתן לחזור למועמדת עליה פסחנו רק בהסתברות אפס.
פרוש זה מציע את ההכללה הבאה: במקום להניח שאי אפשר לחזור למועמדת עליה כבר פסחנו, נניח שניתן לחזור אליה בהסתברות מסוימת שלאו דווקא שווה לאפס.
כמובן, כשההסתברות היא אחת, הבעיה נהפכת לטריוויאלית, משום שנוכל לעבור על כל המועמדות ונחזור לטובה ביותר.
אך כשההסתברות היא בין אפס לאחד, אף על פי שקיים סיכון שלא נוכל לחזור למועמדת שראיינו קודם, כדאי יהיה להמשיך לחפש אפילו שהפתרון המקורי היה אמור להספיק.
אפשר לחשוב על הבעיה של המעסיק באופן הבא: אם יבחר במועמדת הטובה ביותר הוא יזכה בנקודה, ואם יבחר במועמדת אחרת הוא יזכה באפס נקודות.
תחת פירוש זה, הבעיה להגדיל את הסיכוי לבחור במועמדת הטובה ביותר שקולה לבעיה של להגדיל את תוחלת הנקודות שבהן יזכה המעסיק.
פירוש זה מציע את ההכללה הבאה: במקום לתת אפס נקודות לכל מועמדת שאינה המועדפת ביותר, אפשר לתת למועמדת מספר נקודות שתלוי בדירוג שלה; מועמדת יותר טובה תזכה ביותר נקודות.
למשל, המעסיק יזכה ב- נקודות אם יבחר את המועמדת הטובה ביותר, נקודות אם יבחר את המועמדת השנייה הכי טובה, וכן הלאה.
כך אפשר לשאול כיצד תשתנה האסטרטגיה האופטימלית אם נשנה את ה"עונש" עבור בחירה לא נכונה.
במקום להתייחס ל- כמספר קבוע, אפשר לחשוב שהוא עצמו מספר אקראי שלא נגלה לנו מראש אך שהתפלגותו ידועה.
למשל, כשנפרסם מודעה בעיתון, אנחנו יודעים בערך, אך לא בדיוק, כמה מועמדות יבואו.
עכשיו, כשנפסח על מועמדת, יש את הסיכון שלא תהיה מועמדת נוספת ולא נוכל לשכור מזכירה.
בעיית המזכירה לעיל היא מקרה מיוחד של הכללה זו בה ל- יש התפלגות מנוונת.
באלגברה חישובית ובקריפטוגרפיה, בעיית הלוגריתם הבָּדִיד (דיסקרטי) המסומנת בקיצור DLP , היא מציאת המעריך בהינתן הבסיס והתוצאה כך שמתקיים , בקיצור כאשר ו- הם מספרים שלמים.
בניגוד ללוגריתם רגיל מעל המספרים הממשיים שאותו קל לחשב בשיטות המסתמכות על קירוב, קשה לחשב לוגריתם בדיד בקבוצה סופית של מספרים שלמים מודולו שלם כלשהו הנקרא מודולוס.
בעיית הלוגריתם הבדיד בחבורה ציקלית משוערת מזה כמה עשורים כבעיה מתמטית קשה והיא הבסיס למספר אלגוריתמים חשובים בהצפנת מפתח ציבורי כמו פרוטוקול דיפי-הלמן ואלגוריתם חתימה דיגיטלית DSA.
תהי חבורה סופית מסדר .
עבור כל איבר קבוצת החזקות של :
היא תת-חבורה ציקלית של שהסדר שלה הוא השלם הקטן ביותר המקיים .
קל לראות שהרצף חוזר על עצמו כי וכן וכן הלאה.
במקרה זה נקרא יוצר או איבר פרימיטיבי (שורש פרימיטיבי).
אם ראשוני אז היא צקלית וכל איבריה פרט ל-1 הם יוצרים שלה.
לעומת זאת סדר החבורה הכפלית אינו ראשוני (למעט אם ).
לדוגמה לפי אוילר היא מסדר .
לא כל האיברים של חבורה זו הם יוצרים שלה, רואים ש-2 למשל אינו יוצר של החבורה כי והסדר שלו הוא 4 (כלומר אם מעלים את 2 בחזקת עבור רואים שמתקבלת חבורה ציקלית עם ארבעה איברים שחוזרים על עצמם).
כן רואים שלפי חוקי החבורות סדר תת-חבורה תמיד מחלק של סדר החבורה.
אם היא חבורה ציקלית מסדר ראשוני , קיים יוצר של החבורה כך שמתקיים (למעשה יכולים להיות יוצרים רבים).
במילים אחרות, עבור כל שלם קיים שלם ייחודי המקיים .
אם החבורה מובנת מההקשר קוראים ל- "הלוגריתם הבדיד" של בבסיס ואפשר לכתוב זאת בקיצור .
כמו כן אם עבור שלם כלשהו אז .
הסיבה שהלוגריתם נקרא כאן "בדיד" נובעת מהעובדה שהוא נלקח מעל חבורה סופית, זאת בניגוד ללוגריתם רגיל שטווח הערכים שלו הוא מעל קבוצה אין סופית.
לוגריתם בדיד מציית לחוקי הלוגריתמים הרגילים.
למשל, (כאשר '1' הוא איבר יחידה של ) וכן:
הגדרה פורמלית של בעיית הלוגריתם הבדיד היא:
נתונה חבורה ציקלית סופית מסדר המסומנת ב- ונתון יוצר של החבורה ויהי איבר כלשהו.
מצא את הלוגריתם הבדיד של בבסיס בקיצור שהוא איבר יחידי בטווח המקיים: .
ביתר פירוט, נתון אלגוריתם פולינומי יעיל שמקבל את ומחזיר את החבורה , הסדר שלה ויוצר .
מריצים את כדי לקבל את כאשר היא חבורה ציקלית מסדר ו- הוא יוצר של .
בוחרים איבר (אפשר לעשות זאת על ידי בחירת איבר אקראי וחישוב ).
האלגוריתם מקבל את ומחשב את .
הניסוי יוכתר בהצלחה אם אחרת הוא מסתיים בכישלון.
בהגדרה פורמלית, אומרים שבעיית הלוגריתם הבדיד (המסומנת בקיצור DLP) קשה לפתרון ביחס ל- אם עבור כל אלגוריתם פולינומי הסתברותי קיימת פונקציית זניחות כך שמתקיים:
במילים, ההשערה היא שקיימת חבורה שבה בעיית DLP קשה לפתרון מבחינה חישובית למעט בהסתברות זניחה.
אם אז היא חבורה ציקלית מסדר .
אם ניקח יוצר של למשל .
בהינתן השלם , הבעיה היא למצוא המקיים , היות ש- , אז ב-.
הכללה של בעיית הלוגריתם הבדיד
נתונה חבורה ציקלית מסדר ראשוני , המסומנת ב-, ונתונים יוצרים .
בהינתן איבר כלשהו, בעיית ייצוג הלוגריתם הבדיד (discrete logarithm representation problem) בקיצור DLREP, היא למצוא n-יה כך ש-.
n-יה כזו נקראת הייצוג של ביחס ל-.
לדוגמה, ה-n-יה היא הייצוג של 1 ביחס לכל בסיס , והיא נקראת ייצוג טריוויאלי.
בעיית ייצוג הלוגריתם הבדיד נחשבת לבעיה קשה, ובפרט היא קשה יותר מבעיית הלוגריתם הבדיד (אם ניתן לפתור את בעיית ייצוג הלוגריתם הבדיד, אזי ניתן לפתור את בעיית הלוגריתם הבדיד).
בעיית DLREP אטרקטיבית כי אפשר להשתמש בה לצורך חתימה עיוורת.
ויטפילד דיפי ומרטין הלמן פרסמו ב-1976 מאמר פורץ דרך שהעלה לראשונה את רעיון ההצפנה האסימטרית והציעו לבססה על בעיה מתמטית קשה בתורת המספרים הקשורה לבעיית הלוגריתם הבדיד שנקראת כיום בעיית דיפי-הלמן והיא מתחלקת לשתים, בעיית דיפי הלמן חישובית, המסומנת בקיצור CDH ובעיית הכרעת דיפי-הלמן המסומנת בקיצור DDH.
שתיהן בעיות בעלות חשיבות רבה בתחום הקריפטוגרפיה.
נתונה חבורה ציקלית ויוצר ונתונים שני איברים מהחבורה ו- כאשר ו- עבור שני שלמים ו- לא ידועים.
הבעיה הראשונה, בעיית CDH, היא לחשב את פונקציית דיפי-הלמן עבור שני איברים אקראיים (כאשר ו- אינם ידועים אחרת הבעיה טריוויאלית).
הבעיה השנייה DDH היא בעיית הכרעה, להבחין בין פלט הפונקציה לבין איבר אקראי כלשהו מהחבורה.
במילים אחרות עבור איברים שנבחרו באקראי ופתרון אפשרי הבעיה היא להכריע האם או הוא איבר אקראי חסר משמעות.
אם בעיית הלוגריתם הבדיד קלה לפתרון אז אפשר לפתור גם את בעיית דיפי-הלמן, תחילה מחשבים את ואז מחזירים את .
מאידך לא ברור האם קושיה המשוער של בעיית דיפי-הלמן שקול לבעיית הלוגריתם הבדיד.
בעיית DDH נחשבת לבעיה קשה ביחס ל- אם עבור כל אלגוריתם הסתברותי פולינומי קיימת פונקציית זניחות כך שהמתקיים:
במילים פירושו שהבעיה האמורה קשה אם לא קיים אלגוריתם שמצליח להכריע האם בהסתברות משמעותית ביחס לסדר החבורה.
אם נבחר באקראי מתוך באופן בלתי תלוי בערכים אחרים אז האיבר הוא בעל התפלגות אחידה בדידה ב-.
ישנן מספר חבורות בהן בעיית הלוגריתם הבדיד ותאומה בעיית דיפי-הלמן קשות לפתרון.
העדיפות היא לחבורה ציקלית מסדר ראשוני והסיבות הן ראשית משום שידוע שאם סדר החבורה אינו ראשוני אפשר לצמצם את בעיית הלוגריתם הבדיד לבעיה בתת-חבורות שלה שהן יותר קטנות ולכן הפתרון קל יותר.
שנית, קל למצוא יוצר בחבורה מסדר ראשוני כי כל איברי החבורה הם יוצרים.
בנוסף, קל יותר למצוא הופכי כפלי של מעריך כלשהו דבר שרצוי במבנים קריפטוגרפיים מסוימים ובעיקר הסיבה היא שזה הגיוני להשתמש בחבורה מסדר ראשוני כי אם הסדר ראשוני אפשר להוכיח שפלט הפונקציה הוא כמעט אקראי בהשוואה להתפלגות אחידה מעל .
למרות זאת, החבורה הכפלית עם ראשוני נפוצה בישומים מעשיים למרות שסדר החבורה הזו אינו ראשוני.
ההשערה היא שבעיית הלוגריתם הבדיד בחבורה זו קשה גם היא בתנאי שמשתמשים בתת-חבורה מתאימה של .
האיבר הוא שארית ריבועית מודולו אם קיים איבר המקיים .
כך שקבוצת כל השאריות הריבועיות היא תת-חבורה של .
מחצית מהאיברים של החבורה הם שאריות ריבועיות מודולו .
אם הוא מספר ראשוני "חזק", כלומר כאשר ראשוני אז מספר האיברים בתת-החבורה המכילה את כל השאריות הריבועיות מודולו הוא והיות ש- ראשוני תת-חבורה זו ציקלית.
יתרה מזו כל האיברים בתת-חבורה זו הם יוצרים שלה.
כדי למצוא יוצר, פשוט בוחרים איבר אקראי כלשהו שהתנאי הוא שלא יהיה שקול ל- (מודולו ) ואז מציבים מודולו .
דוגמה לבעיית דיפי-הלמן במספרים קטנים
נתון הראשוני החבורה הציקלית מסדר והיוצר .
אם נתונים האיברים ו- (מודולו 97), בעיית דיפי-הלמן היא לגלות את (כאשר ו- לא ידועים), יש לשים לב שאת החזקה מצמצמים מודולו ההסדר של החבורה 96.
חבורה אחרת שבה ההשערה היא שבעיית הלוגריתם הבדיד קשה היא אוסף הנקודות על עקום אליפטי.
היתרון שלו הוא שבניגוד לחבורה כפלית לא ידוע על אלגוריתם שמסוגל לפתור את בעיית הלוגריתם הבדיד בזמן ריצה תת-מעריכי בחבורת העקום האליפטי.
בקצרה, יהי מספר ראשוני ונתונה משוואה ממעלה שלישית בשני נעלמים ו- מהצורה:
כאשר הם קבועים המקיימים את התנאי (תנאי זה הכרחי כדי להבטיח שלא יהיו בעקום קצוות חדים) נניח ש- מייצג את כל הזוגות המקיימים את המשוואה האמורה, אז העקום האליפטי הוא .
במילים, אוסף כל הנקודות המקיימות את המשוואה האמורה עם נקודה מיוחדת הנקראת "הנקודה באין סוף" המסומנת ב-.
קיים כלל חיבור מסובך שמאפשר לחבר שתי נקודות בעקום כדי לקבל נקודה שלישית שגם היא בעקום; או חיבור נקודה בעצמה .
למרבה ההפתעה אפשר להוכיח שקבוצת הנקודות בעקום יחד עם כלל החיבור יוצרים חבורה אבלית.
שהיא חבורה סגורה תחת כלל החיבור כשהנקודה באין סוף משמשת כאיבר יחידה.
לכל נקודה יש נקודה הופכית וכן חוקי האסוציאטיביות והקומוטטיביות מתקיימים בה.
בעיית הלוגריתם הבדיד בעקום אליפטי היא כדלקמן.
נתון עקום אליפטי ונתונה נקודה כלשהי הנקראת נקודת הבסיס וכן הנקודה מצא שלם המקיים .
הקבוצה היא תת-חבורה ציקלית המכילה את אוסף כל הנקודות שהן כפולות של כלומר עד שמגיעים לנקודה באין סוף (נניח שנמצא שלם כך שמתקיים ) הנקודה נמצאת אי שם בחבורה זו כאשר השלם מייצג את מספר הפעמים שהיה צריך לחבר את הנקודה כדי להגיע ל-:
האלגוריתם הטוב ביותר הידוע כיום לפתרון בעיית הלוגריתם הבדיד בעקום אליפטי (אם לא מביאים בחשבון אלגוריתם קוונטי) היא גרסה מקבילית של אלגוריתם רו של פולרד ללוגריתמים.
באופן כללי נתונה חבורה הציקלית עם היוצר והאיבר הבעיה היא מציאת השלם המקיים (בתת-החבורה הנוצרת על ידי או בחבורה אם הוא יוצר שלה), המסומנת בקיצור מודולו הסדר של שנקרא לעיתים הבסיס.
אותה אפשר לפתור בכמה דרכים.
הפתרון הנאיבי ביותר הוא שיטת כוח גס, כלומר אפשר לחשב את כל החזקות של לפי סדר עד שמתקבל .
סיבוכיות הפתרון היא מסדר גודל .
קיימים מספר אלגוריתמים שלהם סיבוכיות טובה יותר והם מתחלקים לשתי קטגוריות.
אלגוריתם גנרי שפועל על כל חבורה ואלגוריתם שפועל רק על חבורה ספציפית.
לצורך הדיון אפשר להתעלם מהחבורה ולהתייחס ישירות לתת-החבורה שהיא מסדר שההנחה היא שהוא מספר ראשוני ידוע.
להלן רשימת האלגוריתמים הידועים לפתרון בעיית הלוגריתם הבדיד וכן בעיית דיפי-הלמן.
אלגוריתם צעד-קטן צעד-גדול של דויד שנקס שמסוגל למצוא לוגריתם בדיד בזמן ריצה של ובסיבוכיות מקום בסדר גודל .
אלגוריתם פוליג-הלמן הוא אלגוריתם ספציפי המתאים במקרה שהגורמים הראשוניים של סדר החבורה ידועים.
במיוחד, אם לסדר החבורה יש גורמים קטנים, אלגוריתם זה מאפשר לצמצם את הבעיה לשתי בעיות לוגריתם בדיד מסדר קטן יותר (לפי גודלם של הגורמים הראשוניים) והפתרונות שלהם ניתנים לשילוב כדי לקבל פתרון לבעיה המקורית בסיבוכיות זמן זהה לבעיות הקטנות.
אלגוריתם רו של פולרד ללוגריתמים שזמן ריצתו הוא בדומה לאלגוריתם צעד-קטן צעד-גדול אך ללא סיבוכיות מקום.
אלגוריתם תחשיב אינדקסים שרץ בזמן ריצה תת-מעריכי ונחשב לאלגוריתם החזק ביותר הידוע כיום לפתרון בעיית הלוגריתם הבדיד בחבורות מסדר גדול מאוד כמו עבור פריק.
גרסה אחת שלו הנקראת אלגוריתם Coppersmith מסוגלת להגיע לזמן ריצה של עבור קבוע כלשהו .
כאשר מחשבים קוונטיים יהיו מעשיים אפשר יהיה לפתור את בעיית הלוגריתם הבדיד בזמן פולינומי עם אלגוריתם שור.
אלגוריתם צעד-קטן/צעד-גדול של דויד שנקס הוא אלגוריתם כוח גס רקורסיבי שעושה שימוש בזיכרון כדי לפתור את בעיית הלוגריתם הבדיד בחבורה ציקלית מסדר בזמן ריצה של .
בהינתן תת-חבורה ציקלית ואיבר , אפשר לדמיין את החבורה כמעגל של האיברים .
ידוע ש- חייב להיות היכן שהוא בתוך המעגל, במקום לחשב ולאחסן בזיכרון את כל האיברים של המעגל עד שנמצא שזה אינו מעשי, "מסמנים" נקודות במעגל במרווחים קבועים (או מדלגים במרחק קבוע) לפי .
במילים אחרות מחשבים ומאחסנים בטבלה ממוינת בזיכרון את האיברים:
כעת היות ש- נמצא באחד מהמרווחים, מובטח שאחד מ- האיברים
יהיה שווה לאחת מהנקודות שאוחסנו בטבלה בזיכרון, שלב זה נקרא "צעד-קטן".
נניח ש- עבור ו- כלשהם, אפשר בקלות לפתור את הלוגריתם על ידי או .
האלגוריתם דורש העלאות בחזקה בחבורה , כל פעולה כזו מתבצעת בזמן של פעולות בסיסיות, אם משתמשים באלגוריתם יעיל לחישוב חזקות בחבורה.
אך יש צורך לאחסן בזיכרון איברים בערך.
למעשה ברקורסיה, למעט האיבר הראשון לחישוב כל איבר נדרשת פעולת כפל אחת: באופן דומה כל ניתן לחישוב כ-.
מיון ניתן לביצוע בזמן של וחיפוש בינארי מתבצע בזמן של .
קלט: תת-חבורה , האיבר וסדר החבורה .
ממיינים את כל הזוגות () לפי הערך השני.
אם עבור כלשהו מחזירים את מודולו .
בחבורה מסדר , אם ו- כדי לחשב את הלוגריתם הבדיד של 17 בבסיס 2 תחילה מחשבים את ואז מכינים טבלה עם זוגות הערכים הבאים (מודולו 29) ממוינת לפי הערך השני:
ואז מחשבים את הערכים הבאים עם המונה :
בחיפוש מהיר מסתבר שהערך האחרון שהתקבל זהה למעשה לכניסה הרביעית בטבלה לכן מודולו 29.
בלוגריתם בדיד, בדומה לפירוק לגורמים, ישנן שתי פעולות הופכיות שאינן סימטריות בכוח החישוב הדרוש לביצוען.
לדוגמה, כפל ופירוק לגורמים הם פעולות הפוכות, בעוד שכפל היא פעולה קלה במונחי מחשוב, הרי שפירוק לגורמים קשה הרבה יותר ממנה.
כן הדבר בלוגריתמים, העלאה בחזקה מודולרית (מודולו שלם ) קלה הרבה יותר ממציאת החזקה מודולו .
חוסר הסימטריה הזה נקרא פונקציה חד-כיוונית, והיא מנוצלת היטב בעיקר בהצפנה אסימטרית.
דוגמאות הן: פרוטוקול דיפי-הלמן להעברת מפתח, צופן אל-גמאל, חתימה דיגיטלית של אל-גמאל ואלגוריתם חתימה דיגיטלית DSA.
כדי להתמודד עם האיום של האלגוריתמים המנויים לעיל, ההנחה היא כיום שראשוני בגודל 2048 סיביות מספק מרווח ביטחון סביר.
תקן DSA מגדיר למשל מספר רמות אבטחה לאלגוריתם חתימה דיגיטלית כשהמרבית היא, p ראשוני בסדר גודל של 3072 סיביות.
בעיית המחסור היא מושג יסודי בכלכלה המבטא את ההבדל שבין רצונות הפרטים לבין כמות המשאבים המוגבלת במשק.
מוצרים שאינם במחסור לא ייחשבו למוצרים כלכליים.
אין חוסר באוויר, למשל, ולכן הוא אינו מוצר כלכלי, אך לעומתו זהב נמצא בכמות מוגבלת, ולכן הוא מוצר כלכלי.
מתופעת המחסור נובע שכל החלטה לייצר מוצר כלכלי מסוים כרוכה בוויתור על ייצור מוצר אחר.
כלל זה הוא הבסיס לשלוש שאלות היסוד של הכלכלה, לעקומת התמורה, לעלות האלטרנטיבית ולעוד עקרונות ומושגים בתורת הכלכלה.
שלוש שאלות היסוד של הכלכלה הן שלוש השאלות שכל משק נאלץ לשאול:
3. בשביל מי לייצר – מי יצרוך את המוצרים?
בשוק חופשי, תקבענה התשובות על שאלות אלו על ידי ביקוש והיצע לכל מוצר.
בשוק שבו יש רשות מרכזית מתכננת (רוסיה הסובייטית למשל) יקבעו התשובות על ידי הרשות או הממשלה.
עקומת התמורה מבטאת את בעיית המחסור באופן גרפי: אם נניח כמודל משק שבו קיימים שני מוצרים בלבד, ארונות ואוניות, הרי שהעקומה היא אוסף נקודות הייצור המקסימליות של המשק — נקודות שמהן הגדלת הייצור בענף אחד כרוכה בהקטנת הייצור בענף השני — וגבול יכולת הצריכה במשק סגור.
הימצאות על העקומה בנקודה כלשהי פירושה ניצול אופטימלי של גורמי הייצור.
עלות אלטרנטיבית היא הוויתור על ייצור מוצר אחד הכרוך בייצור מוצר אחר.
לדוגמה, בשרטוט הנ"ל בשביל לייצר A אוניות המשק ויתר על ייצור חלק מהארונות והסתפק בייצור F ארונות.
הוויתור הזה נקרא עלות אלטרנטיבית כוללת, נוסף על כך ישנן עלות אלטרנטיבית ממוצעת: העלות הכוללת חלקי A — מספר האוניות שיוצרו; ועלות אלטרנטיבית שולית אשר מודדת על כמה ארונות ויתרנו במחזור ייצור בשביל להוסיף למחזור הייצור של האוניות את האוניה האחרונה.
בעיית הנציג , מתייחסת למצב בו נציג הנדרש לייצג בפעולותיו אדם או גורם כלשהו, ישתמש בסמכויותיו כדי לקדם אינטרסים שונים מהאינטרסים של האדם או הגורם אותו הוא מייצג.
בעיה זו מופיעה במצבים בהם מתקיים מידע א-סימטרי בין המנהל המאציל סמכות כלשהי לבין הנציג אשר מקבל את אותה סמכות.
במונחים כלכליים הבעיה מהווה סוג מסוים של כשל שוק, כלומר היא גורמת לחוסר יעילות בהתנהלות הכלכלית במשק.
בדיני תאגידים קיימת התייחסות לבעיה
היועץ מעוניין למקסם אינטרסים אישיים, והנועץ מעוניין לקבל מידע יעיל וחף מאינטרס זר
הבעיה במשל היא של מנהל וסוכן המכירות.
בעוד המנהל מעוניין למקסם את הרווח, הסוכן שנמדד על המכירות שלו, מעוניין במיקסום המכירות.
הבעיה של המנהל היא כיצד למנוע מהסוכן להוריד מחירים כדי להגדיל את המכירות כאשר הורדה זו פוגעת ברווח.
יש כאן בעיית מידע לא סימטרי.
הסוכן יודע יותר טוב מהמנהל את גמישות הביקוש של הלקוחות והוא יציג אותה למנהל כגמישה מאוד ולכן לא כדאי להעלות מחירים.
אף על פי שייתכן והביקוש הוא קשיח יותר והעלאת המחירים תקטין מעט את המכירות אבל תגדיל את הרווח.
בעיית הנציג והבנק המרכזי האירופי
הבנק המרכזי האירופי (European Central Bank) הוא הבנק המרכזי של המדינות החברות באיחוד המוניטרי האירופי, הוא אחראי על המדיניות המוניטרית, האירו, ושער הריבית באיחוד המוניטרי.
הבנק משרת 17 מדינות החברות באיחוד המוניטרי ופועל באופן עצמאי ומנותק מהדרג הפוליטי שלהן.
בדומה לצורה בה עובד בנק ישראל בארץ מאז נחקק חוק בנק ישראל, ובדומה לשיטה האנגלו-סקסית הנהוגה בבריטניה, ארצות הברית וקנדה.
בשנת 2002 החוקר רוברט אלג'י (Robert Elgi) טען כי עצמאות הבנק המרכזי האירופי כפי שנקבע באמנת מאסטריכט (Treaty of Maastricht) בשנת 1992, ולאחר מכן הורחבה ובוססה באמנת אמסטרדם (Treaty of Amsterdam) בשנת 1999, היא סוג של בעיית נציג המתקיימת בין הבנק המרכזי לבין המדינות באיחוד.
לפי אלג'י, הנציג הוא הבנק המרכזי הנשלח עלי די הבנקים המרכזים של המדינות והמדינות עצמן כדי לנהל את המדיניות המוניטרית של האיחוד.
עבור ניהול זה נתנו המדינות בידי הבנק סמכויות וחובות המופרטות באמנות השונות.
המנהל במקרה שלנו הוא המדינות כמובן.
עקרון היסוד מאחורי הקמת הבנק היה עצמאות הבנק המרכזי וחוסר ההתערבות של מדינות האיחוד והממשלות המקומיות בהתנהלותו של הבנק.
עקב כך נוצר מצב בו הבנק המרכזי יכול לפעול לפי שיקול דעתו, ואף למען האינטרסים שלו, בניגוד מוחלט לאינטרסים של המדינות שיצרו אותו עבורן.
אלג'י מביא מספר דוגמאות שלדעתו מוכיחות שהבנק פעל בצורה שכזאת.
לפי אמנת מאסטריכט, מטרת העל של הבנק המרכזי האירופי היא שמירה על יציבות מחירים במדינות האיחוד.
בנוסף לאותה מטרה ישנן מטרות משניות שהאמנה קבעה שעל הבנק למלא ולעמוד בהן.
המטרות מגיעות בעיקר בתחום של מחקר כלכלי, ותמיכה בקידום החלטות כלכליות של מוסדות האיחוד המוניטרי.
בפועל הבנק המרכזי בחר להתעלם מהמחויבויות הנוספות שדרשה ממנו האמנה.
אלג'י טוען שהבנק בחר לפרש את האמנה על באופן שיתאים לאינטרסים שלו, ולכן התמקד בעיקר בסוגיית יציבות המחירים.
יתרה מכך, נשיא הבנק המרכזי הראשון ווים דויזנברג (Wim Duisenberg) הכריז מספר רב של פעמים כי אינו רואה חשיבות או מחויבות של הבנק המרכזי לעמוד בשאר היעדים שנקבעו לו, מעבר ליעד של יציבות המחירים.
אלג'י מרחיב את הרעיון של בעיית הנציג אותה הדגים על הבנק המרכזי האירופי וטוען, שאפשר לומר שסוגיית הגירעון הדמוקרטי באיחוד האירופי היא מקרה מורחב של בעיית הנציג.
זאת מכיוון שברוב המקרים, מוסדות האיחוד האירופי לא נבחרו על ידי האזרחים עצמם, אלא על ידי שליחים של שליחים.
בנוסף, ברוב המקרים הם פועלים עבור מטרות של האיחוד האירופי ולטובת האיחוד האירופי, שהוא הנציג, ולא לטובת המדינות או האזרחים שהוא המנהל, ובכך פוגעים במטרה לשמה נועדו בצורה מובהקת.
בעיית הנציג בארגונים בין ממשלתיים
ארגונים בין ממשלתיים הם תופעה שקיימת מאות שנים, לאורך כל ההיסטוריה הקימו מדינות ארגונים בהן היו חברים נציגים של הממשלות במטרה לקדם אינטרסים ברמה הבינלאומית.
למרות זאת במאה האחרונה ובייחוד מאז סוף מלחמת העולם השנייה התרחבה התופעה באופן אדיר.
הגידול בכמות הארגונים הבין ממשלתיים בשנים האחרונות צמח לגידול כמעט מעריכי.
ארגונים בין ממשלתיים הם זרוע של המדינות שהקימו אותם, שבהם יושבים נציגים של המדינות, ובניגוד לארגונים על-ממשלתיים סמכותם אינה מעל למדינות.
למרות כל זאת ישנם חוקרים שטוענים שהמבנה, המרחב והצורה בה פועלים ארגונים בין ממשלתיים גורמים להם לסטות מהתפקיד המקורי עבורו נוצרו ולפעול לטובת האינטרסים שלהם, בדיוק כמו בבעיית הנציג, כאשר הארגונים בתפקיד הנציג והמדינות בתפקיד המנהל.