tomron87/hebrew-wikipedia-sentences-corpus huggingface dataset:
נשים לב שבבעיה המקורית, אם כל סכום אפשרי של מספרים יכול להיכתב באמצעות P ביטים, אם נפתור את הבעיה המקורית באלגוריתם הקירוב עם , נפתור את הבעיה בדיוק.
לכן אלגוריתם זה הוא פתרון מדויק של הבעיה כשהוא רץ בזמן פולינומי ב- וב- (כלומר, אקספוננציאלי ב-).
האלגוריתם רץ בזמן פולינומי כיוון שהרשימות S, T, U תמיד בגודל פולינומי ב-n וב-, ולכן גם כל הפעולות שנעשות עליהן מתבצעות בזמן פולינומי.
גודל הרשימות אכן נשאר פולינומי היות שאנו מוסיפים עצמים ל-S אם הם גדולים מהעצם הקודם ב- וקטנים מ-.
הצעד שמוודא שההפרש בין כל שני עצמים שמתווספים הוא לפחות מוודא שברשימה יש לכל היותר עצמים.
האלגוריתם נכון כיוון שבכל צעד מתווספת שגיאה של לכל היותר , ובמהלך שלבים מתווספת שגיאה של לכל היותר .
בעיית הספיקות בתחשיב הפסוקים (בקיצור: SAT - קיצור של המילה האנגלית Satisfiability, שמשמעותה ספיקות) הוא שמה של בעיית הכרעה הנחקרת במסגרת תורת הסיבוכיות במדעי המחשב.
בעיה זו הייתה הבעיה הראשונה עליה הוכח כי היא NP-שלמה (הוכחה זו היא משפט קוק-לוין), משמע אם קיים לה פתרון אלגוריתמי הרץ בזמן פולינומי אזי קיים פתרון כזה לכל בעיה ב-NP (מחלקת כל הבעיות שעבורן קיים מוודא בזמן פולינומי).
בעיה זו משמשת בהוכחות רבות עבור בעיות NP-שלמות אחרות.
בלוגיקה מתמטית נהוג לומר על נוסחה בתחשיב פסוקים שהיא ספיקה אם קיימת השמה של ערכי אמת עבורה הנוסחה היא אמיתית.
למשל, הנוסחה "A או B" היא ספיקה, כי ניתן לקבוע את ערכו של A ל"אמת" וערך האמת שיתקבל עבור הנוסחה כולה יהיה "אמת" גם הוא.
לעומת זאת, הנוסחה "A וגם לא A" אינה ספיקה, כי לא ייתכן כי גם "A" וגם "לא A" יהיו יחד בעלי הערך "אמת".
באופן כללי, בעיית SAT היא הבעיה הבאה: בהינתן נוסחה בתחשיב הפסוקים שמכילה רק קשרים מסוג "גם", "או" ו"לא", האם קיימת השמה של ערכי אמת למשתנים כך שהנוסחה תקבל ערך אמת?
ניתן להראות שגם אם נגביל את הבעיה לנוסחאות הניתנות בצורה הנורמלית הקוניונקטיבית (CNF), הבעיה תישאר NP-קשה.
לכן, בשל נוחות העבודה עם נוסחאות בצורת CNF, מקובל לנסח את הבעיה רק עבור נוסחאות הנתונות בצורה זו (וריאנט זה של הבעיה נקרא לעיתים CNF-SAT או CSAT).
לבעיית ה-SAT חשיבות בתחומים רבים של מדעי המחשב, ובהם אלגוריתמיקה, בינה מלאכותית ותכן חומרה.
מקובל להתייחס בשם לבעיית סיפוק נוסחאות בצורת CNF אשר כל הפסוקיות המופיעות בהן מאורך .
ניתן לראות כי הבעיות ו ניתנות לפתרון בזמן פולינומי.
(כלומר, שייכות ל-P), בעוד שעבור הבעיה המתקבלת NP-שלמה (כלומר, צמצום הבעיה לפסוקיות מאורך בלבד לא הופך אותה לקלה יותר)
בעזרת למת המקומיות של לובאס ניתן להראות כי אם כל משתנה מופיע בלכל היותר פסוקיות, אזי קיימת השמה מספקת.
מאידך, ייתכן כי לא ניתן למצוא את ההשמה המספקת בזמן פולינומי.
בהינתן נוסחת CNF בעלת פסוקיות, ניתן לשאול מה מספר הפסוקיות המקסימלי אשר ניתן לספק באמצעות השמת ערכי אמת.
(אם הנוסחה ספיקה, מספר זה הוא ) בעיה זו מכונה בעיית ספיקות מקסימלית.
(באנגלית, Max-Sat) ניתן להוסיף ולהכליל בעיה זו באמצעות קביעת משקל לכל פסוקית, ומציאת השמת ערכי אמת עבורה משקל הפסוקיות המסופקות יהיה מקסימלי.
גרסה זו של הבעיה נקראת בעיית הספיקות המשוקללת המקסימלית.
נמצאו אלגוריתמי קירוב רבים לבעיות אלה, אשר נותנים קירובים שונים, (1/2, 2/3, 3/4 ואף יותר מכך), אך הוכח בשנת 1997 כי לא ייתכן אלגוריתם פולינומי אשר מבטיח פתרון טוב יותר מאשר 7/8-קירוב.
(אלא אם כן P=NP) לכן, שייכות הבעיות Max-Sat ו-Max-W-Sat למחלקה APX אך לא ל-PTAS.
(אלא אם כן, P=NP, ואז שתי המחלקות הנ"ל שוות)
בעיית כיסוי קבוצות היא בעיה קלאסית בקומבינטוריקה, מדעי המחשב, אופטימיזציה וסיבוכיות.
הבעיה נכללת ברשימת 21 הבעיות ה-NP שלמות של קארפ.
בעיית כיסוי הקבוצות היא בעיה חשובה בתחום אלגוריתמי קירוב.
היא בעיה ש"לימודה הוביל לפיתוח טכניקות יסודיות לתחום הכולל" של אלגוריתמים מקורבים.
הבעיה היא: נתונה קבוצה סופית של קבוצות סופיות, שאיחודן הוא הקבוצה .
יש למצוא תת-קבוצה של בגודל מינימלי, שאיחוד הקבוצות בה הוא .
כלומר יש למצוא את הכיסוי הקטן ביותר לקבוצה שהוא תת-כיסוי של .
שאלה זו היא NP-קשה; וגרסת בעיית ההכרעה שלה היא NP-שלמה.
הבעיה הזו היא דוגמה אופיינית וחשובה של בעיית אופטימיזציה בדידה.
תכונה חשובה של בעיה בסיסית זו היא שניתן למצוא באופן יעיל קירוב סביר לאופטימום שלה - ניתן למצוא באופן יעיל פתרון לבעיה הקרוב לפתרון האופטימלי, בסיבוכיות שתהיה בסדר גודל של הלוגריתם של גודל הקבוצה שאותה יש לכסות.
בהינתן קבוצה וקבוצה של תתי קבוצות של , כיסוי הוא תת-קבוצה כך שאיחוד האיברים של הוא .
הבעיה היא למצוא את הכיסוי המינימלי של (כלומר הכיסוי שמשתמש בכמה שפחות איברים מ-).
בגרסת בעיית ההכרעה של בעיית כיסוי הקבוצות נתון הזוג ומספר טבעי , והשאלה היא האם יש תת-קבוצה של מגודל לכל היותר שמהווה כיסוי של .
בהנחה ונתונה לנו קבוצה ומשפחה של קבוצות .
איחוד של כל הקבוצות ב- מכיל את כל האלמנטים ב-.
לעומת זאת כיסוי הקבוצות הקטן ביותר עבור מקרה זה יהיה: .
הצגה כבעיית תכנון ליניארי בשלמים
ניתן להציג את בעיית כיסוי קבוצות כבעיית תכנון ליניארי בשלמים כך:
מזער את (מזער את מספר הקבוצות)כאשר לכל (כל איבר ב- מכוסה על ידי קבוצה אחת לפחות) לכל ( אם איבר בכיסוי ו- אם לא)
הדרך הפשוטה ביותר לבצע את זה היא על ידי אלגוריתם קירוב חמדני.
באלגוריתם זה בונים תת-קבוצה של כדלקמן: מתחילים מקבוצה ריקה ומצרפים לה מדי צעד איבר מ- (שהוא למעשה תת-קבוצה של ) המגדיל ככל האפשר (בשלב הנוכחי) את מספר האיברים באיחוד האיברים שכבר נבחרו (מוסיפים את האיבר שיכסה כמה שיותר איברים מ- שעדיין לא כוסו).
האלגוריתם משיג יחס קירוב של (כלומר הוא מוצא פתרון שקטן מ- פעמים גודל הכיסוי האופטימלי).
כאשר הוא המספר ההרמוני ה--י.
ו- הוא גודל הקבוצה שאותה צריך לכסות, כלומר .
למעשה ניתן להוכיח שהאלגוריתם משיג יחס קירוב של כאשר הוא גודל האיבר הגדול ביותר ב- (כיוון שכל איבר ב- הוא למעשה תת-קבוצה של ).
לחלופין, ניתן למצוא קירוב טוב לפתרון בהסתמך על תכנון ליניארי בשילוב עם תהליך של עיגול מקרי.
במדעי המחשב, בעיית הפילוסופים הסועדים היא המחשה לבעיות תזמון ותיאום שמופיעות בהקשרים של עיבוד מקבילי - מספר תוכניות שרצות יחד וחולקות משאבים משותפים.
בשל פשטותה היחסית, הבעיה מוצגת לעיתים קרובות בקורסים בסיסיים העוסקים בנושאים הללו.
את הבעיה הציפה שאלה שנוסחה בשנת 1971 על ידי אדסחר דייקסטרה, ולאחר מכן הומחשה באמצעות הסיפור הציורי של הפילוסופים.
חמישה פילוסופים יושבים סביב שולחן עגול ומבלים את זמנם בחשיבה ובאכילה.
במרכז השולחן ישנה קערת ספגטי גדולה, ולכל אחד מהפילוסופים יש צלחת.
בין כל שתי צלחות נמצא מזלג, כך שישנם בסך הכול חמישה מזלגות.
על מנת לאכול את הספגטי, כל פילוסוף זקוק לשני מזלגות (בניסוחים אחרים של הבעיה המזלגות מוחלפים במקלות אכילה).
כל פילוסוף יכול להרים רק את שני המזלגות הקרובים אליו (אלו שמימין ומשמאל לצלחת שלו) ואינו יכול להרים את שניהם בו-זמנית - כלומר, עליו להרים את אחד מהם, ורק לאחר מכן את השני.
תנאי נוסף הוא שלא מתקיימת כל תקשורת בין הפילוסופים.
שתי הבעיות הבסיסיות שעלולות להתהוות הן קיפאון והרעבה.
מצב של קיפאון מתרחש כאשר כל הפילוסופים נתקעים במצב כלשהו ממנו אינם יכולים לצאת.
מצב של הרעבה מתרחש כאשר אחד או יותר מהפילוסופים אף פעם אינו מצליח לאכול.
דוגמה נוספת להרעבה מתרחשת כאשר מוסיפים למערכת אלמנט של עדיפות.
פתרון אפשרי, למשל, למצב הקיפאון שתואר לעיל תספק החלטה שפילוסוף האוחז מזלג ומחכה למזלג אחר, ישחרר את המזלג שבידו אם שכנו מבוגר ממנו וגם הוא מחזיק מזלג.
זהו פתרון טוב למדי, אך הוא יכול להביא למצב שבו הפילוסוף הצעיר ביותר אינו מספיק אף פעם לאכול, בעוד הפילוסופים משני צדדיו אוכלים לסירוגין.
הפילוסופים מייצגים תהליכים ותהליכונים שרצים במקביל על מעבדים שונים או על מעבד יחיד.
המזלגות מייצגים משאבים משותפים - זיכרון מחשב, קבצים וכדומה.
פתרון פשוט יחסית מושג על ידי הפעלה של "מלצר" בשולחן.
פילוסוף חייב לבקש רשות להרים מזלג.
מפני שהמלצר מודע למצב המזלגות, הוא מסוגל להכריע ולמנוע מצב של קיפאון (Deadlock).
כאשר ארבעה מזלגות בשימוש, הפילוסוף הבא שמעוניין לבקש מזלג, צריך לחכות לרשות המלצר, שכמובן לא תינתן עד אשר המזלג יתפנה.
הלוגיקה פשוטה על ידי הקביעה שפילוסופים קודם כל מרימים את המזלג השמאלי ואחר כך את הימני (או להפך).
המלצר מתנהג כסמפור, רעיון שהוצג על ידי דייקסטרה ב-1965.
נאפשר לפילוסוף להרים את המזלגות שלו באופן הבא, ללא מעורבות של צד שלישי: נשים צלחת מרכזית על השולחן, כל פילוסוף שירצה להרים את המזלגות שלו יצטרך ראשית לקבל שליטה על הצלחת ורק לאחר מכן יוכל להרים את המזלגות.
פתרון זה מקטין את רמת המקביליות המתאפשרת במערכת, ולכן מאריך את משך ההמתנה עבור הפילוסופים.
כמו כן, הפתרון מונע מצב של קיפאון, אך לא מצב של הרעבה.
בתורת החבורות, בעיית וייטהד היא השאלה הבאה: האם כל חבורה אבלית שעבורה מתקיים התנאי , היא חבורה אבלית חופשית?
(הסימון מתייחס לפונקטור הנגזר Ext).
בעיה זו נחשבה לאחת הבעיות המרכזיות בתורת החבורות, עד שהתברר ב-1971 שהיא בלתי כריעה במסגרת האקסיומות הרגילות של תורת הקבוצות.
פירושו של התנאי הוא שכל הרחבה , מתפצלת.
במילים אחרות, לכל חבורה אבלית ואפימורפיזם שהגרעין שלו הוא חבורה ציקלית אינסופית, קיים מונומורפיזם כך שההרכבה היא העתקת הזהות של .
אם מקיימת תנאים אלו, היא נקראת חבורת וייטהד.
בעיית וייטהד, אם כך, שואלת האם כל חבורת וייטהד היא חופשית (אין לחבורות האלה קשר לחבורות או ).
את השאלה הציג ג'ון וייטהד בשנות ה-50 של המאה ה-20, בהקשר לבעיית Cousin השנייה.
תשובה חיובית עבור חבורות בנות מנייה ניתנה זמן קצר אחר-כך.
ההתקדמות בקשר לחבורות גדולות יותר הייתה איטית, והבעיה נחשבה לאחת החשובות ביותר באלגברה.
ב-1973 הראה שהרן שלח שהבעיה בלתי תלויה באקסיומות הרגילות של תורת הקבוצות, אקסיומות ZFC.
ביתר פירוט, הוא הוכיח ש:
אם כל הקבוצות ניתנות לבנייה, אז כל חבורת וייטהד היא חופשית;
אם מניחים את אקסיומת מרטין ואת שלילת השערת הרצף, אז יש חבורות וייטהד לא חופשיות.
אם מניחים שאקסיומות ZFC יוצרות מערכת עקבית, אז גם המערכת הכוללת את אקסיומת הבנייה, שקובעת שכל הקבוצות ניתנות לבנייה, היא עקבית.
מצד שני, אקסיומת מרטין עקבית עם שלילת השערת הרצף.
יחד, שתי התוצאות מראות שבעיית וייטהד אינה ניתנת להכרעה.
תוצאה זו הייתה לחלוטין בלתי צפויה.
קיומן של טענות בלתי כריעות היה ידוע מאז 1931, כאשר קורט גדל הוכיח את משפט האי-שלמות שלו.
עם זאת, דוגמאות לטענות כאלה, שהבולטת שבהן היא השערת הרצף, היו בדרך כלל מוגבלות לתחומי תורת הקבוצות.
הפעם הכתה האי-שלמות באחד המבצרים של המתמטיקה המודרנית, תורת החבורות.
ב-1980 הראה שלח שגם אם מניחים את השערת הרצף, בעיית וייטהד נשארת בלתי כריעה.
כמה וכמה תוצאות אחרות של אי-כריעות עבור בעיה זו המחישו באופן חד את התלות של התאוריה של החבורות האבליות שאינן בנות מנייה, באקסיומות של תורת הקבוצות שמעליהן מוגדרות החבורות.
במתמטיקה, התפוצצות קומבינטורית מתארת גידול מהיר מאוד של פונקציות, כתוצאה משיקולים קומבינטוריים.
דוגמאות לפונקציות כאלה הן: פונקציית העצרת, פונקציית אקרמן וכדומה.
במדעי המחשב משתמשים במושג התפוצצות מצבים לתיאור בעיית מספר רב מאוד של מסלולי בקרה בתוכנה, כתלות בקלט שלה.
הכוונה היא לתוכנה (המהווה למעשה פונקציה רב ערכית, אשר מקבלת קלט ומחזירה פלט כתוצאה מעיבוד הקלט), המחזירה מספר פלטים שונים, שגדל בצורה מהירה מאוד, עבור מספר קלטים שגדל לאט.
כשמדובר על אימות תוכנה אוטומטי עבור כל קלט, ישנה מגבלה של זמן ומקום, המונעת, בגלל בעיית התפוצצות המצבים, אפשרות להבטיח כיסוי קוד מלא בבדיקות תוכנה.
בעיית הקרונית או דילמת הקרונית היא בעיה באתיקה הממחישה את הסתירה בין התפיסה התועלתנית לבין התפיסה הדאונטולוגית באתיקה.
את הבעיה הציגה לראשונה הפילוסופית פיליפה פוט בשנת 1967.
נתונות שתי קבוצות של עובדים על מסילת רכבת: האחת בת חמישה עובדים, השנייה בת עובד אחד.
קרונית שועטת במהירות לעבר קבוצת 5 העובדים.
לא ניתן לעצור את הקרונית לחלוטין, אך ניתן להסיטה ממסלולה אל עבר אדם אחד.
האם המעשה הנכון יהיה לתת לדברים להתרחש בלי התערבות ולאפשר את הריגתם של חמישה אנשים חפים מפשע, או להטות את הרכבת ולהביא למותו של חף מפשע אחד?
הדילמה מייצגת שתי השקפות בפילוסופיה, דאונטולוגיה ותועלתנות.
לפי ההשקפה התועלתנית יש למדוד בחירות, פעולות או כוונות, רק על סמך התוצאה שבאה בעקבותן.
על פי עקרון התועלת, הבחירה המוסרית היא זו המפיקה את כמות האושר הגדולה ביותר, או את כמות הסבל הקטנה ביותר.
לכן, על פי הגישה התועלתנית יש להסיט את הרכבת.
ביקורת אחת על גישה זו היא שהתועלתנות מאפשרת כל פעולה על מנת למקסם את כמות האושר, גם אם היא אכזרית ומבוצעת על חפים מפשע.
על כן גם בווריאציות קיצוניות של הדילמה כמו דחיפת אדם שמן למסילת הרכבת או הריגת אדם וקצירת אבריו על מנת להציל חמישה אנשים אחרים, יש לבחור באותו האופן.
ביקורת נוספת היא שאין מקום בגישה זו למחויבות המוסרית הייחודית שיש לאדם כלפי קרוביו וחבריו.
התועלתנים מציעים פתרונות לביקורות כגון אלו, ביניהם פתרון של הבחנה בין חובות חיוביות לשליליות.
מצד אחד החובה לעשות את העולם טוב יותר ולמקסם את האושר אך מצד שני החובה לא לעשות את העולם גרוע יותר ולכן לא להרוג על מנת להציל.
על פי הגישה הדאונטולוגית לעומת זאת, יש בחירות שלא ניתן להצדיק על ידי השפעתן והן אסורות מבחינה מוסרית.
מוסריות הפעולה לא נקבעת על פי תוצאותיה, אלא על פי אופי הפעולה עצמה.
לעיתים אדם צריך לעשות פעולה גם אם אינה ממקסמת את הטוב.
הביקורת כנגד הגישה הדאונטולוגית היא חוסר הרציונליות הקיים בה.
לדוגמה, האם במקרה בו מוצבים על פסי הרכבת מיליון אנשים במקום חמישה, הייתה משתנה הדילמה באופן מהותי?
לפי הגישה הדאונטולוגית אין הבדל בין המקרים, זאת מפני שמוסריות המעשה לא נקבעת על פי השלכותיו.
דיונים פילוסופיים אלו רלוונטיים גם היום בנושאים כמו הפלות, עונש מוות וניהול ענייני רווחה.
בעיה דומה שתוארה, ממחישה את הדילמה בצורה חריפה אף יותר: נתונים חמישה עובדים על מסילת רכבת.
מעליהם עומד איש שמן, וצופה בנוף.
רכבת קרבה ולא ניתן לעצור אותה, אלא על ידי דחיפתו של האיש השמן לעצור את הקרון.
האם יהיה נכון לשלוח את האיש השמן אל מותו כדי להציל חמישה אנשים אחרים?
גרסה אלטרנטיבית של ג'ודית ג'רביס תומסון שלא כוללת רכבת, מתוארת כך:
מנתח המתמחה בהשתלת איברים מטפל בחמישה חולים, שכל אחד מהם זקוק לאיבר אחר וימות ללא השתלה.
אין איברים זמינים לביצוע אף אחת מחמש ההשתלות הללו.
מטייל צעיר ובריא, שרק עובר בעיר בה עובד הרופא, נכנס לבדיקה שגרתית במרפאה.
במהלך ביצוע הבדיקה מגלה הרופא כי איבריו תואמים את כל חמשת חוליו הגוססים.
נניח בנוסף שאם הצעיר ייעלם, לא יחשדו ברופא.
האם תתמכו במוסר הרופא להרוג את אותו תייר ולספק את איבריו הבריאים לאותם חמישה אנשים גוססים ולהציל את חייהם?
לפי קווין דאטון, השיפוט המוסרי של אנשים בבעיה אתית זו ובווריאציית הקרונית והאיש השמן שלה, תלוי, בין היתר, במבנה המוח שלהם.
לטענתו, פסיכופתים יעדיפו את אותה האופציה בשני המקרים (להרוג איש אחד בלבד), מאחר שמרכזי הרגש פגועים במוחותיהם, וריאציה זו של הבעיה מערבת שיקולים רגשיים, בניגוד לגרסה המקורית של הבעיה.
ישנם מחקרים בתחום מדעי המוח (באמצעות FMRI) הבוחנים את השיפוט המוסרי של המוח העשויים לתמוך בטענתו, מאחר שהם מצאו מעורבות של רגשות בשיפוט המוסרי של המשתתפים.
ניסוי אמפירי של דילמת הקרונית
במחקרים הרוב המוחלט של הנשאלים אומרים שהיו מסיטים את המסילה כדי להרוג אדם אחד על פני חמישה.
ב-2017 ארגן בלוגר המדע מייקל סטיבנס ניסוי מעשי כדי להתרשם מה בני אדם עושים בפועל בסיטואציה זו.
שבעה אנשים השתתפו בניסוי, במחשבה שהם עומדים להשתתף בקבוצת מיקוד על כבישים בלוס אנג'לס.
כל אחד הגיע בנפרד והוזמן להמתין בתא בקרה מזויף של רשות הרכבות, שבו ישב אדם שתפקידו להסיט רכבות ממסלול אחד לשני לפי הצורך.
מול שולחן הבקרה היו מסכי טלוויזיה שבהם נראו המסלולים כביכול בשידור חי, אך למעשה הוקרנו בהם סרטי וידאו שהוכנו מראש.
בעת ההמתנה בקר הרכבות הלבבי הסביר למשתתפים את עבודתו והם למדו איך להסיט את הרכבת ממסילה אחת לשנייה.
בשלב מסוים יצא הבקר מהחדר, ואז ראה המשתתף במסכים את התרחיש של דילמת הקרונית.
על מסילה אחת היו חמישה אנשים, על המסילה השנייה אדם אחד, ובכריזה נשמעה אזהרה שיש חפץ על המסילה ורכבת מתקרבת.
מתוך הקבוצה אישה אחת וגבר אחד משכו את המתג והסיטו את הרכבת.
מיד לאחר מכן הוקרנה לכל המשתתפים שקופית "הניסוי הסתיים, אף אדם לא נפגע".
כאשר האנשים העומדים על המסילה הם יהודים, מצד אחד גרימת מוות לאחד עשויה להיכלל באיסור לא תרצח ומצד שני יש חובת הצלת אדם מישראל מדין לא תעמוד על דם רעך.
כאשר אדם אחד גורם סכנה לאדם אחר ניתן להציל את האדם בסכנה גם על ידי הריגת המסכן, מדין רודף, אך במקרה שלנו הסכנה לרבים לא נובעת מקיומו של היחיד במסילה השנייה.
בתוספתא נדון מקרה דומה של הצלת רבים על ידי מסירת יחיד: "סיעה של בני אדם שאמרו להם נכרים: תנו לנו אחד מכם ונהרגהו, ואם לאו – הרי אנו הורגין את כולן, יהרגו כולן ואל ימסרו להם נפש אחת מישראל.
אבל, אם ייחדוהו להם, כגון שייחדו לשבע בן בכרי - יתנוהו להם ואל יהרגו כולן."
החזון איש התלבט האם ההלכה המופיעה בתוספתא תקפה גם במקרה של חץ העושה דרכו לעבר קבוצת אנשים וניתן להטותו לעבר אדם אחד: מצד אחד במסירת אדם הפעולה היא סיוע להריגה ואין בה באופן מהותי קשר להצלה ואילו בהסטת החץ הפעולה היא פעולת הצלה וההריגה של האדם היא במקרה.
מצד שני, הסטת החץ היא פעולה אקטיבית של הריגה ואילו מסירת אדם להריגה על ידי אחר אולי שונה.
בשו"ת ציץ אליעזר הכריע ששב ואל תעשה עדיף ויש להימנע מפעולה במצב שתגרום מוות, גם אם תציל רבים.
הרב שאול ישראלי כתב באופן נחרץ יותר: "בשום פנים ואופן אסור להציל, אפילו רבים וחשובים, כשהצלתם מחייבת הריגתו (או אפילו גרם הריגתו) של אחד שאילולא זה לא היה נהרג.
העובר על זה והרג אדם מישראל לצורך הצלת אחד או אפילו רבים, דינו כדין רוצח".
במדעי המחשב, בעיית יצרן צרכן היא דוגמה קלאסית לתיאור בעיית סינכרון בין שני תהליכים או יותר הנגרמת במערכות המאפשרות ריבוי משימות.
הבעיה נגרמת כאשר שני תהליכים או יותר חולקים חוצץ המוגבל בגודלו.
חלק מהתהליכים אחראים להכניס מידע לחוצץ (יצרנים) וחלק אחראים לשלוף ממנו מידע (צרכנים).
פתרון הבעיה דורש מנגנון שימנע משני תהליכים לעדכן בו-זמנית את אותה רשומה, בעזרת שימוש בסנכרון בין התהליכים.
פתרון לא מספק יגרום בחלק מהמקרים למצב של קיפאון, כאשר שני התהליכים "ישנים" וממתינים ש"יעירו" אותם.
פתרון אפשרי לבעיה מתבצע באמצעות סמפורים או מוניטורים.
כאשר יש יותר מיצרן אחד וצרכן אחד, יש להשתמש גם במנעול.
בעיית "Min cost flow" היא בעיית אופטימיזציה שמטרתה מציאת הדרך הזולה ביותר להעברת זרימה בגודל מסוים ברשת זרימה קיימת.
בהינתן, רשת זרימה כאשר צומת מקור, צומת בור
וקשת בעלת קיבולת , זרימה ומחיר .
מחיר העברת הזרימה בקשת הוא .
מטרת הבעיה היא להעביר כמות נתונה של זרימה מקודקוד המקור (s) לקודקוד הבור (t), כך שהמחיר הכולל,
הפתרון נדרש לקיים את אילוצי הזרימה הבאים:
| שימור זרימה (שימור חומר): || for all
| שימור גודל הזרימה הנדרש: || and
הכללה ובעיות הקשורות לבעיית Min cost flow
גרסאות אחרות של בעיה זו מדברות על מציאת זרימה מקסימלית בעלת המחיר הקטן ביותר מבין כל הזרימות המקסימליות האפשריות, בעיות מסוג זה נקראות "minimum cost maximum flow".
הכללה של בעיה זו היא minimum cost circulation problem שבעזרתה ניתן לפתור את הבעיה הנדונה.
זה נעשה על ידי חסימת ערכי קיבולות הקשתות ברשת על ידי 0 (חסם תחתון) והוספת קשת נוספת בעלת קיבולת וחסם תחתון , (המחברת ישירות את קודקוד הבור (t) חזרה לקודקוד המקור (s)) אשר קובעת את הזרימה הכוללת להיות .
את הבעיה ניתן לחלק למקרים פרטיים בהם אילוצי הקיבולת מוסרים (ולכן הבעיה הופכת לבעיית מציאת המסלול הקצר ביותר),
ומקרים בהם אנו מתעלמים ממחיר הזרימה (ולכן מחיר הזרימה דרך כל אחת מהקשתות שווה), בהם נקבל את בעיית הזרימה המקסימלית.
בעיית min cost flow ניתנת לפתרון על ידי תכנון ליניארי, מאחר שאנו מחפשים אופטימיזציה לפונקציה ליניארית וכל האילוצים הם פשוטים.
כמו כן, קיימים אלגוריתמים קומבינטורים לפתרון הבעיה כאשר חלקם הכללות של אלגוריתמים לחיפוש ומציאת זרימה מקסימלית ברשת וחלקם האחר נוקט בגישות אחרות שונות.
אלגוריתמים ידועים (שקיימים במספר וריאציות שונות) לפתרון הבעיה הם:
בעיית הרוע או בעיית הרע היא סוגיה תיאלוגית-פילוסופית, העוסקת בשאלה העקרונית, כיצד קיימים רוע וסבל בעולם, בהתחשב בהנחה המקובלת בדתות רבות (ובכללן היהדות) שאלוהים הוא טוב ורוצה להיטיב.
לסוגיה השלכות לא רק בדיון הפנים דתי, אלא גם בהקשרים רחבים יותר כגון הוכחה מהיות הרוע לנכונות האתאיזם (שלילת האל) ועוד.
בספרו "דיאלוגים על הדת הטבעית", מצטט הפילוסוף דייוויד יום את הטיעון כסדרה של שאלות, המיוחסות במקור לפילוסוף היווני אפיקורוס:
בעיית הרוע נוגעת גם בסוגיות הצדק.
הדיון על בעיית הרוע הורחב גם מעבר לסבל האנושי, אל הסבל של חיות הבר בטבע.
במהלך הזמן ובאסכולות חשיבה שונות, הוצעו פתרונות שונים לבעיה ובהם:
הגישה הדואליסטית - גישה זו דוגלת בהיות שני כוחות בסיסיים בבריאה, המהווים שני קטבים - טוב ורע.
אלוהים נמצא בצד הטוב והוא אכן מיטיב בלבד, אך קיים גם הצד הרע והוא הגורם לסבל ולרוע הנפוצים בעולם.
גישה זו סותרת את התשתית הרעיונית של הדתות המונותואיסטיות.
הגישה המונותואיסטית - גישה זו שוללת קיומו של יותר מאל אחד, ומייחסת הן את הטוב והן את הרע לאלוהים.
על פי הגישה, את הרע מייצר האדם בעקבות חטאיו ברשות האל.
תפיסה זו "מנקה" את האל ממעמדו כרע, ותולה אותו באדם.
גישת הטוב הכללי - על פי גישה זו, האל הוא מקור הטוב היחיד והמוחלט , ומקרי הרוע בהם האדם נתקל נובעים מהקושי שלו לראות את התמונה כולה, וכן מקושי להבין באמת מהו טוב ומהו רע.
לעיתים גישה זו מדגישה כי בעתיד יידע האדם להבחין ולדעת מהו טוב ורע, ואף יבין למפרע מדוע מה שהיה נראה לו רע במהותו הוא טוב.
בעיית הרוע ביהדות מוכרת בניסוח השאלה "מדוע צדיק ורע לו, רשע וטוב לו", ומהווה נקודת דיון יסודית בתורת הגמול.
שאלה זו מנוסחת בגמרא במסכת ברכות, בה מסופר כי משה שאל את אלוהים: "מפני מה יש צדיק וטוב לו ויש צדיק ורע לו, יש רשע וטוב לו ויש רשע ורע לו?".
המקרא עצמו עוסק גם הוא בבעיית הרוע באריכות בספר איוב, ובהמשך עסקו בה חז"ל והוגים יהודים רבים.
השואה חידדה לרבים את בעיית הרוע, היות שהתרחשותה גרמה לרבים משבר אמוני, סביב השאלה כיצד אלוהים טוב, איפשר לדברים איומים כאלו להתרחש.
בעיית התיחום היא בעיה בפילוסופיה של המדע המתייחסת לקושי שבמציאת כללים או קריטריונים שלפיהם ניתן יהיה להבחין באופן חד משמעי בין המדעים האמפיריים מחד גיסא לבין תאוריות לא מדעיות, ובמיוחד לצורך הבחנה ברורה וחד משמעית בין אמת מדעית לבין תאוריות אשר מתיימרות להיות מדעיות, אך אשר אינן מדעיות.
כמו כן בעיית התיחום עוסקת גם במאבק המתמשך בין המדע והדת, ובמיוחד באלמנטים שונים של הדוקטרינה הדתית אשר לדעת רבים יכולים וצריכים להיות נתונים לביקורת מדעית.
זהו אחד הנושאים המרכזיים בפילוסופיה של המדע אשר לא נפתרו לחלוטין עד היום.
הפוזיטיביזם הלוגי גורס כי רק קביעות המבוססות על תצפית אמפירית הן בעלות משמעות, ובמשתמע גורס כי כל קביעה המבוססת על אופן אחר של היקש או היסק, כולל קביעות מטאפיזיות הוא חסר משמעות.
הפילוסוף האוסטרי-בריטי קרל פופר דחה עיקרון זה של הפוזיטיביזם הלוגי והציע במקומו את עקרון ההפרכה לפיו היפותזה חייבת שיהיו לה מסקנות תצפיתיות שניתן להעמידן בניסיונות הפרכה, ורק אז היא נחשבת מדעית.
עיקרון זה ספג ביקורת מאנשים כמו תומאס קון, שטען כי ניתנות להפרכה לא שחקה תפקיד סיבתי משמעותי במעבר בין תאוריות מדעיות.
הפילוסוף היהודי-הונגרי אימרה לָקָטוֹש, אשר היה מתלמידיו של פופר, הציע קריטריון נוסף על עקרון ההפרכה שמבחין בין תוכניות חקר פרוגרסיביות ודגנרטיביות.
בעיית הסחטן הוא מושג בכלכלה ובמשפטים המתאר מצב בו ישות יכולה לסחוט ישות אחרת בכוח שגדול מכוחה האמיתי.
הבעיה היא בעיה מתורת המשחקים בה לעיתים עסקה יעילה מחייבת הסכמה של גורמים רבים, שלכל אחד מהם יש זכות וטו.
במצב זה, העסקה עלולה לא לצאת לפועל עקב דרישות מופרזות של אחד הגורמים.
דרישות אלו ייתכנו כאשר ישנו מידע חסר ביחס לתביעות אשר העלו גורמים אחרים, או ביחס לערך אותו מעניק הצד השני לעסקה.
בעיית הסחטן משקפת כשל שוק הנובע ממודל של בחירה רציונלית.
עבור עסקאות מסוימות, השקעות שנעשות לצורך בדיקת כדאיות העסקה הן השקעות ייחודיות המתאימות רק לעסקה הספציפית (investment specific), במובן זה שלא ניתן להחזירן במלואן או בכלל, במידה והחוזה לא יוצא אל הפועל.
כך, להשקעות אלו אין ערך מחוץ למערכת החוזית בין הצדדים.
ההוצאות הללו נקראות "הוצאות שקועות".
בכך הוא מגדיל את חלקו בעוגה החוזית על חשבונו של הצד השני.
כך למעשה נוצרת "בעיית הסחטן" (hold-up problem).
מצב זה של השקעה טרומית נמוכה מזו האופטימלית מכונה השקעת חסר (under-investment), או הסתמכות חסר (under-reliance), והוא נראה כמעט בלתי נמנע במצב בו צד למשא ומתן נדרש להשקיע השקעה טרומית, כאשר היקף ההשקעה היא פונקציה של הערך העודף שהשקעה זו תניב לו מהעסקה.
במצב בו אין כל הגנה על הוצאות הסתמכות טרום חוזיות, כך שהסיכון להפסיד את השקעות הללו מגולגל במלואו על אותו צד שמשקיע אותם.
הסתמכות טרום חוזית תהפוך ליקרה יותר, נדירה יותר וסבירה פחות, עד אשר תיעלם כליל.
בהיותנו מונחים על ידי מטרה נורמטיבית של יעילות כלכלית, נראה כי אין מנוס מהמסקנה המקדמית כי יש לאמץ משטר כלשהו המטיל אחריות כלשהי על השקעות טרום חוזיות בנסיבות מסוימות.
סיכון מוסרי זה מתעורר במקרה זה שכן המסתמך "מבוטח" בפני הפסד השקעתו ומסיבה זו הוא מתעלם מהעלויות החברתיות שפעולותיו גורמות.
עם זאת, ניתן לפתור זאת באמצעות כלל פשוט לפיו תחת דוקטרינת ההשתק: אדם שהשקעת ההסתמכות שלו עולה על הסכום שבית המשפט יכיר בו כסביר, לא יקבל חזרה את מלוא הוצאותיו, אלא, רק את אותו חלק שהוכר כסביר.
בצורה זו יאלץ המסתמך ביתר לשאת בהפרש בעצמו.
לכאורה, הגבלה שכזו מספקת את התמריץ להימנע מהסתמכות יתר.
הניתוח הכלכלי למשפט תקף בעיה זו והגיע לשתי מסקנות עיקריות הקשורות ומשולבות אחת בשנייה:
ראשית, מצופה מן הצדדים כי יתגברו על הבעייתיות שבהסתמכות-חסר על ידי מנגנונים או תניות חוזיות ראויות, כגון: חוזה על תנאי, קנסות ביטול, אופציות חוזיות, הצעות בלתי הדירות וכדומה.
פתרון שני הוא באמצעות דוקטרינת ההשתק וזאת על ידי יישום מנגנון שיאפשר לצדדים לכבול את עצמם באופן אמין בהתחייבות שלא לפעול בדרך אופורטוניסטית, לאחר שהצד השני ישקיע בהוצאות הסתמכות.
כך, יישום ופרשנות מתאימים מצד בתי המשפט של דוקטרינת ההשתק והחובה לנהוג בדרך מקובלת ובתום לב במהלך משא ומתן, יכולה להוביל את הצדדים לרמת השקעה אופטימלית, על ידי הכרה בהתנהגות אופורטוניסטית המתבטאת בניצול עמדת מיקוח עדיפה, כפי שבאה לידי ביטוי בבעיית הסחטן, כהפרה של חובת תום הלב במשא ומתן.
בעיה זו תפטר רק כאשר ידע ביהמ"ש להבחין בין הסתמכות יעילה אשר הרווחים הצפויים ממנה עולים על ההפסדים, לבין עלויות הסתמכות שיש בהן יותר נזק מתועלת, כך שהצד שהוציא אותן מוכן היה לעשות זאת רק אם יקבל עליהן פיצוי.
ברוח גישה זו טוען Craswell כי דיני ההצעה והקיבול יפורשו כך שיראו במשא ומתן חוזה תקף לכל דבר, אם יש צורך בכך על מנת לתמרץ צד לחוזה להסתמך באופן אופטימלי בשלב הטרום חוזי, זאת על מנת להעניק לו את הביטחון והוודאות הדרושים לו על מנת לבצע השקעות שכאלו.
Katz טוען ברוח דומה כי יראו הבטחה הניתנת על ידי צד למשא ומתן כמחייבת מכוח דיני ההשתק, כאשר מתן התוקף להבטחה יועיל להביא את הצדדים להשקיע באופן יעיל בהוצאות ההסתמכות.
לשם כך, לדעת Katz, יש לבחון בדיעבד מה היו יחסי הכוחות בין הצדדים בזמן ההשקעה, על ידי בחינה בידי מי מצוי המידע הרלוונטי לעסקה ובידי מי חלק הארי של כוח המיקוח.
הטלת ההגבלות הנ"ל על כוחו של צד למשא ומתן לנצל את עמדת המיקוח העדיפה שלו לאחר השקעתו של הצד השני בהוצאות הסתמכות, מחליפה למעשה את רצון הצדדים וההסכמה המשתמעת שלהם בעניין זה.
גישות אלו, המתבססות על יעילות כלכלית כהצדקה להטלת אחריות טרום חוזית, הופכת להיות יותר ויותר מקובלות, בייחוד בקרב האסכולה הכלכלית לדיני החוזים.
בדוגמת המפעל הנדרש לשיפורים טכנולוגיים או לרכישת מכונות ייצור חדישות על מנת לזכות בחוזה מסוים, ייתכן כי ההוצאה לא תחשב כשקועה, מאחר שהיא אינה ספציפית עבור העסקה הנדונה.
זאת בהנחה כי המפעל יוכל בעתיד להפיק רווחים מהשיפור באמצעות התקשרויות אחרות, מכירת המכונות וכו'.
דיון נוסף בהסתמכות יתר ראו עופר גרוסקופף וברק מדינה.
הם מדגישים את בעיית הסתמכות היתר, שלטענתם סביר יותר שתתעורר כאשר מדובר בשחקנים חד פעמיים וחסרי ניסיון בשוק שיש בו תחרות.
לטענתם יש הצדקה להתערבות משפטית על מנת למזער בעיה זו, לא פחות מאשר ההצדקה במקרים של הסתמכות חסר.
מנגד, ישנם מלומדים הסבורים כי הסתמכות יתר אינה בעיה "אמיתית" בניתוח הכלכלי של דיני החוזים.
בקריפטוגרפיה, בעיית הפצת מפתחות (key distribution problem) ובעיית תחזוקת מפתחות, הן בעיות העוסקות בהיבטים קריפטוגרפיים של העברה, ניהול ותחזוקה של מפתחות-הצפנה סודיים באופן בטוח בין שתי ישויות או יותר המתקשרות ברשת.
לאור העובדה שבפרוטוקול הצפנה העושה שימוש באלגוריתם סימטרי כדי להצפין את תעבורת הרשת, יש צורך להעביר את מפתח ההצפנה מהשולח למקבל כדי שהאחרון יוכל לפענח את המסרים שקיבל.
אם יפול מפתח ההצפנה לידי צד שלישי ('אויב' או 'מתחרה') במהלך ההעברה, הדבר משפיע מיידית על ביטחון הפרוטוקול: היריב יכול להשתמש במפתח זה כדי לפענח את כל תעבורת הרשת שהוצפנה באמצעותו.
שמירת מפתחות הצפנה בסוד מחייבת הפעלת אמצעים קריפטורפיים או פיזיים כמו כספת כדי להגן עליהם מפני חשיפה.
בעיה זו מחריפה אף יותר כאשר מספר המשתתפים גדול.
לצורך המחשה, כאשר 15 משתמשים מעוניינים לנהל התקשרות בטוחה ביניהם, הם צריכים בסך הכול 105 מפתחות, כשכל משתמש צריך להחזיק ב-14 מפתחות.
מספר זה גדל באופן מעריכי ככל שמספר המשתתפים עולה.
בניסוח כללי, עבור רשת של משתמשים נדרשים בסך הכול מפתחות.
ברשת מרובת משתמשים אין שום דרך מעשית לאחסן מספר כה גדול של מפתחות בסודיות.
המשתתפים בהתקשרות משתמשים בערוץ פתוח, כלומר רשת תקשורת הנגישה לכל אדם, כגון רשת האינטרנט, כך שההנחה היא שאפשר לצותת להם בקלות.
הבעיה נובעת מהעובדה שאין בידי המשתתפים ערוץ בטוח כדי לשתף בו את מפתח ההצפנה ביניהם.
ייתכן שלא נפגשו מעולם ואף אינם מכירים זה את זה.
העברת המפתח על ידי שליח גם היא לא בטוחה לגמרי ואף אינה מעשית אם הם רחוקים זה מזה.
הם יכולים להעביר את מפתח ההצפנה בדרכים אחרות כמו באמצעות הדואר או הטלפון, אולם גם אמצעים אלה ניתנים לניטור בדרכים פשוטות.
מלבד זאת, אם קיימת דרך בטוחה להעברת מפתח ההצפנה, ייתכן שהמשתתפים יוכלו לנצלה כדי להעביר את המידע עצמו ואז לא יהיה צורך בהצפנה כלל.
בעבר, כאשר ההצפנה שימשה בעיקר צבאות, דיפלומטים ומרגלים, העברת המפתח הסודי בוצעה במפגש אישי או על ידי בלדר שהיה נאמן על הצדדים.
אולם במסחר הנעשה דרך רשת האינטרנט, הכולל אינספור עסקאות או פעולות, שיטה זו אינה מעשית.
פרוטוקול שפותר את בעיית הפצת המפתחות נקרא בכללות פרוטוקול שיתוף או יסוד מפתח (Key establishment) והוא אלגוריתם הכולל סדרה של מהלכים או חילופי מסרים בין שני משתתפים או יותר ברשת תקשורת פתוחה, שבסיומם המשתתפים הלגיטימיים משתפים ביניהם מפתח סודי כך שהם סמוכים ובטוחים שמלבדם אין איש יודע מהו.
בעיקרון אפשר להשתמש בו כמפתח הצפנה להצפנת ההתקשרות ביניהם באמצעות אלגוריתם סימטרי מהיר כמו AES, אולם כדי לא לחשוף את אלגוריתם ההצפנה לחולשות שעלולות להיות במפתח שנגזר, מומלץ לא להשתמש בו ישירות אלא לגזור ממנו מפתח אחר באמצעות פונקציית גזירת מפתח (Key derivation function) בקיצור KDF.
לדוגמה אפשר להשתמש בפונקציית גיבוב.
המפתח הסודי המשותף שנגזר בסופו של דבר נקרא בדרך כלל מפתח שיחה, כשמו הוא נועד להתקשרות אחת או מספר התקשרויות מוגבל ובגמר השימוש בו המפתח מושמד.
באופן כללי קיימים שני סוגי פרוטוקולים;
שיתוף מפתח (Key agreement); שני משתתפים או יותר מסכימים ביניהם על מפתח סודי כך שכל אחד מהם תורם את חלקו להקמתו במידה שווה.
העברת מפתח (Key transport); צד אחד מייצר ומעביר מפתח סודי למשתתפים האחרים, בעוד שהם אינם בהכרח תורמים להקמתו ואין להם שליטה עליו.
בפרוטוקול מודרני נוסף מרכיב אימות זהויות כדי למנוע התקפת אדם באמצע על הפרוטוקול.
אפשר להוסיף אימות על ידי חתימה דיגיטלית ותעודות מפתח ציבורי (certificate) החתומות על ידי רשות מאשרת.
אולם העדיפות היא לאימות עקיף כחלק אינטרגלי ללא צורך בתהליכים נפרדים או בסיוע צד שלישי.
אפשר לחלק את מרכיב האימות לשני סוגים:
אימות חד צדדי, שבו צד אחד משתף ומאמת מפתח עם צד אחר, כך שהוא מקבל אישור לזהותו של המשתתף האחר.
אימות דו צדדי, בפרוטוקול שבו תהליך האימות מספק אישור זהותם של כל הצדדים המשתתפים בפרוטוקול כלפי האחרים.
בין יתר האלמנטים שפרוטוקול קריפטוגרפי לשיתוף מפתח אמור לתת מענה הם, התקפות פסיביות שבהן התוקף מנסה לנחש את המידע הסודי על ידי התבוננות בחילופי המסרים בין המשתתפים הלגיטמיים שמתבצעים כאמור בערוץ פתוח שניתן לציתות.
והתקפות אקטיביות שבהן התוקף שמסוגל בנוסף ל'הזריק', ליירט, למחוק, לשנות ואו לשכפל מסרים.
ביתר פירוט פרוטוקול שיתוף מפתח אמור לתת מענה לאיומים הבאים:
מפתח ידוע (known-key); הפרוטוקול ייוותר בטוח נוכח מצב שבו נחשפו לעיני התוקף מפתחות שיחה ישנים (שנוצרו בעבר על ידי הפרוטוקול).
שמירת סודיות קדימה (forward secrecy) או סודיות מושלמת קדימה; גם אם מפתח אימות ארוך-טווח של אחד המשתתפים נחשף, הדבר לא ישפיע על סודיות מפתחות שיחה שנוצרו בעבר לפני החשיפה.
שליטה; אף אחד מהצדדים לא יוכל לאלץ את מפתח השיחה שיהיה ערך כלשהו לפי בחירתו (כמו ערך המכיל חולשות נסתרות).
קיימות שתי דרכים עיקריות לשיתוף מפתח.
צד שלישי הנקרא בהקשר זה KDC - קיצור של key distribution center.
הוא שרת ייעודי שתפקידו לייצר ולהפיץ מפתחות הצפנה סודיים עבור כל המשתמשים ברשת.
תחילה המשתמשים משתפים מפתח הצפנה סודי עם שרת ה-KDC כל אחד מהם בנפרד והוא מצידו מנהל רשימה ארוכת טווח של מפתחות סודיים של כל המשתמשים הרשומים.
לאחר מכן לפי דרישה, מפיק ושולח מפתח שיחה זמני וחד פעמי, כשהוא מוצפן תוך שימוש במפתחות ההצפנה המתאימים למשתמשים שמעוניינים להתקשר ביניהם ובגמר השימוש בו המפתח מושמד.
היתרונות בשיטה; כל משתמש נדרש לזכור רק מפתח סודי אחד ארוך טווח, אותו הוא משתף עם שרת המפתחות.
הוספה או הסרה של משתמש מתבצעת מול שרת המפתחות בלבד.
אין צורך ליצור קשר עם משתמשים אחרים.
חסרונות השיטה; במקרה ששרת המפתחות מותקף, כל המפתחות בסכנה.
אם ההתקפה מצליחה כל המשתמשים חשופים לחלוטין.
כאשר שרת המפתחות קורס מסיבה טכנית כלשהי התקשורת נעצרת לחלוטין.
פרוטוקול קרברוס הוא פרוטוקול העברת מפתח מעשי וחינמי שהומצא ב-MIT ונועד לשיתוף מפתחות הצפנה על ידי צד שלישי נאמן המשמש כשרת מפתחות.
הפרוטוקול פופולרי מאוד והוא בשימוש נרחב במערכות ההפעלה חלונות ומקינטוש.
ב-1976 פרסמו ויטפילד דיפי ומרטין הלמן מאמר מפורסם בשם "new directions in cryptography" בו הם הסבירו לראשונה אסטרטגיה שונה להפצת מפתחות שנקראה לאחר מכן בשם פרוטוקול דיפי-הלמן.
השיטה מבוססת על פרדיגמה שנקראת "מפתח ציבורי" או "הצפנה א-סימטרית".
כל משתמש מייצר שני מפתחות, האחד פרטי וסודי והשני ציבורי.
ההצפנה מתבצעת עם המפתח הציבורי והפענוח עם המפתח הפרטי.
לכל מפתח פרטי קיים מפתח ציבורי אחד ויחיד שמתאים לו.
כך שאם מתבצעת ההצפנה במפתח הראשון, ניתן לפענח את התוצאה עם המפתח השני ולהפך.
בדרך זו המשתמשים יכולים לפרסם ברבים את מפתחות ההצפנה הציבוריים שלהם, כך שיהיו נגישים לכל.
כאשר אליס מעוניינת להתקשר עם בוב אף שמעולם לא פגשה בו, כל שעליה לעשות הוא להשיג את המפתח הציבורי של בוב מהרשימה הציבורית, להפיק מפתח שיחה חד פעמי ולהצפינו באמצעותו ולשולחו לבוב בערוץ הפתוח.
רק בוב יכול לפענח את המסר, לחלץ ממנו את מפתח השיחה הסודי ואיתו להתקשר עם אליס בצורה בטוחה.
קיימת הבחנה בין המפתחות הציבוריים הארעיים (ephemeral key) שנוצרים לצורך הפרוטוקול ומשמשים להכנת מפתח השיחה לבין המפתחות ארוכי-טווח שברשות המשתתפים שנועדו לאימות זהותם.
בדרך כלל רצוי שהמשתתפים בפרוטוקול יאמתו את המפתחות הציבוריים ארוכי הטווח שלהם.
ישנן שתי דרכים לכך, האחת אימות מוקדם באמצעות צד שלישי כמו רשות אישורים, זאת בטרם יחלו במהלכי הפרוטוקול.
והשני שילוב חתימה דיגיטלית בכל מסרי הפרוטוקול.
יתרונות השיטה; המשתמשים אינם צריכים להפגש כלל ואין צורך בניהול והחזקה של מספר גדול של מפתחות.
הצטרפות או הסרה של משתמש אינן דורשות מאמץ מיוחד, כל שיש לעשות הוא להוסיף או להסיר את המשתמש המתאים ברשימה הציבורית.
כל שיחה מתבצעת עם מפתח טרי וחד פעמי אותו משמידים בגמר השיחה.
חסרונות השיטה; עדיין נדרש תהליך אימות כדי לוודא שמפתח ציבורי שייך למי שמתיימר להיות בעליו.
כל ניסיון מוצלח להונות משתמשים אחרים באמצעות מפתחות מזויפים יכול להביא לפריצת הרשת לחלוטין.
RSA היא שיטת הצפנה א-סימטרית מעשית שנמצאת בשימוש נרחב בכל מערכת הצפנה מודרנית והיא מנוצלת בעיקר להעברת מפתחות הצפנה.
בשתי הדרכים האמורות קיימת בעיית אימות והבטחת שלמות (message authentication).
גם אם המשתמשים מוצאים דרך בטוחה להעביר ביניהם מפתח סודי לצורך הצפנת תעבורת הרשת, אין הם יכולים להיות בטוחים שהמידע העובר ברשת אותנטי, כלומר שהוא מגיע מהמקור הנטען וכי לא בוצע בו שינוי במהלך ההעברה אם בגלל שגיאה טכנית או בשל מהלך זדוני (malicious) על מנת לפרוץ את המערכת.
את בעיית האימות ניתן לפתור גם כן בשתי דרכים;
קוד אימות מסרים העושה שימוש בצופן בלוקים או פונקציית גיבוב כדי לייצר הצפנה מאומתת.
דוגמאות מעשיות אפשר למצוא למכביר; כמו CBC-MAC או HMAC.
או בשיטות מתקדמות יותר כמו OCB או GCM.
DSA הוא אלגוריתם חתימה דיגיטלית שהתקבל כתקן רשמי והוא נפוץ בפרוטוקולי תקשורת רבים.
דיפי והלמן, היו הראשונים שחידשו את קונספט החתימה הדיגיטלית המוכר כיום אמצעי קריפטוגרפי יעיל ובטוח להבטחת אימות ושלמות מידע.
תוצר נלווה של חתימה דיגיטלית הוא שניתן למנוע מהחותם להכחיש בשלב יותר מאוחר שחתם על מידע נתון.
דיפי והלמן אמנם לא הציעו רעיון מעשי לחתימה דיגיטלית אך כשנה לאחר מכן פרסמו ריבסט שמיר ואדלמן את RSA שהיה לאלגוריתם המעשי הראשון שיכל לשמש הן להצפנה והן לחתימה דיגיטלית.
פתרון נוסף שנותן מענה חלקי לבעיה הוא אלגוריתם חלוקת סוד.
בשיטת חלוקת סוד, מפתח ההצפנה יכול להיות מוצפן ומחולק בין מספר משתתפים באופן כזה שרק בשיתוף פעולה של מספר מוגדר של משתמשים ניתן לשחזרו.
ללא מספר החלקים הדרוש (או ה'שתפים' בהקשר של חלוקת סוד) אין דרך לשחזר את המפתח.
הגדרה פורמלית של ביטחון פרוטוקול שיתוף מפתח
אליס ובוב מעוניינים לשתף ביניהם מפתח הצפנה סודי באמצעות פרוטוקול שיתוף מפתח .
פרמטר ראשון שעליהם להסכים הוא (אורך המפתח בסיביות).
כל אחד מהם מטיל מטבע במספר הפעמים הדרוש כדי לייצר מחרוזת אקראית באורך ומריץ את הפרוטוקול בערוץ פתוח שנתון לציתות.
בגמר הפרוטוקול אליס ובוב מפיקים מפתחות הצפנה סודיים בהתאמה.
ולצורך הנכונות, הפרוטוקול הסתיים בהצלחה אם בכל הטלת מטבעות והרצה של הפרוטוקול.
במילים אחרות אליס ובוב כעת משתפים ביניהם מפתח סודי, כאשר בהגדרה המצותתת איב לא תוכל לנחש בזמן פולינומי מהו מתוך התבוננות במהלכי הפרוטוקול.
ביטחון הפרוטוקול מוגדר במונחים של ניסוי אותו אפשר לתאר בקיצור: .
הסבר: אליס ובוב מריצים את הפרוטוקול בנוכחות איב (eavesdropper) המצותתת להם ומסומנת בקיצור כשבידי כל אחד מהם מחרוזת סיביות אקראית בגודל .
תוצאת הרצת הפרוטוקול היא עותק המכיל את מהלכי הפרוטוקול והמסרים שעברו מצד לצד וכן מפתח המשותף לשני הצדדים.
לצורך הניסוי מטילים מטבע, דהיינו בוחרים סיבית אקראית ובודקים:
אם , בוחרים מחרוזת באופן אקראי ואחיד.
נניח שקיים אלגוריתם שמקבל כקלט עותק של מהלכי הפרוטוקול ואת הסיבית ומפיק את .
תוצאת הניסוי מוגדרת '1', דהיינו האלגוריתם הסתיים בהצלחה אם אחרת התוצאה היא אפס.
פרוטוקול שיתוף מפתח ייקרא בטוח בנוכחות המצותתת איב, אם עבור כל - אלגוריתם הסתברותי פולינומי, קיימת 'פונקציית זניחות' של המסומנת בקיצור כך שמתקיים:
כלומר ההסתברות ש- יחזיר את ובכך יאפשר ליריב לגלות האם , גדולה מחצי בשיעור שאינו עולה על פונקציה זניחה כלשהי של .
פונקציית זניחות יכולה להיות למשל מהצורה .
בתורת החבורות, בעיית הצמידות היא בעיית הכרעה שבאה לקבוע האם שני איברים בחבורה בעלת הצגה הם צמודים.
בעיה זו ובעיות דומות נוספות באות לידי ביטוי בעולם ההצפנה, והן מהסיבות לבטיחותם של פרוטוקולי הצפנה שונים.
בהינתן חבורה G עם הצגה, בעיית הצמידות מוגדרת כך - בהינתן שני איברים x,y של G, האם קיים איבר c של G עבורו מתקיים .
האיבר c נקרא המצמיד של x ו-y.
לבעיה זו יש משמעות רק בחבורות לא אבליות, משום שבחבורה אבלית מחלקות הצמידות היחידות הן היחידונים.
בתורת החבורות מספר בעיות מפורסמות דומות, ביניהן בעיית המילה.
בעיית הצמידות קשורה לבעיית המילה ולמעשה מהווה תנאי מספיק עבורה - כדי לדעת האם שתי מילים w,v שקולות, מספיק לדעת האם צמודה לזהות.
בעיה נוספת שנובעת ישירות מבעיה זו, היא בעיית חיפוש המצמיד, שמטרתה לא רק לקבוע האם קיים מצמיד, אלא גם למצוא אותו.
בעיית צמידות החזקות (power conjugacy problem) שואלת (בהינתן חבורה מוצגת סופית ושני איברים בה) האם לאברים יש חזקות צמודות.
בעיה זו אינה תלויה בבעיית הצמידות: יש חבורות שבהן בעיית הצמידות פתירה ובעיית צמידות החזקות אינה פתירה, ולהפך.
עולה השאלה הטבעית, האם תמיד אפשר לפתור את הבעיה, כלומר האם בכל חבורה נוצרת סופית אפשר לקבוע האם כל שני איבריה צמודים.
התשובה לכך היא שלילית, כלומר עבור חבורות רבות הבעיה היא לא כריעה.
ובכל זאת, ישנן חבורות רבות עבורן הבעיה פתירה, ביניהן חבורה חופשית, חבורת הצמות, חבורה היפרבולית ועוד רבות.
היותה של הבעיה פתירה אין הכוונה שהיא פתירה בקלות - כלומר לחבורות שונות (כמו חבורת הצמות) קשה מאוד למצוא איבר מצמיד (אפילו מתת-חבורה נתונה), כלומר לבעיה סיבוכיות קשה.
לבעיה זו ולבעיות דומות מתורת החבורות יש קשר הדוק להצפנה ולבטיחות פרוטוקולי הצפנה שונים בחבורות לא קומוטטיביות.
הקושי בפענוח צפנים טומן בתוכו את הקושי בפתרון בעיית הצמידות.
בחבורות בהן סיבוכיות בעיית הצמידות ובעיית חיפוש המצמיד קשה יש שימוש נרחב בפרוטוקולי הצפנה רבים, כמו בפרוטוקולים של Anshel–Anshel–Goldfeld ו-Ko–Lee et.
בעיית חיפוש המצמיד מכונה לעיתים בעיית לוגריתם בדיד, ובכך קושי פתירתה אנלוגי לקושי במציאת לוגריתם בדיד בחבורות אבליות, כמו בפרוטוקול דיפי-הלמן.
בעיית השלשות הפיתגוריות הבוליאנית היא בעיה מתמטית במסגרת תורת רמזי, העוסקת בצביעה של המספרים הטבעיים תחת אילוצים.
לבעיה נמצאה במאי 2016 הוכחה בעזרת מחשב, שהתפרסמה בעיתונות הפופולרית כהוכחה "הארוכה ביותר בעולם".
הבעיה שואלת האם יש צביעה בוליאנית (בשני צבעים, למשל אדום וכחול) של המספרים הטבעיים, כך שלא תימצא אף שלשה פיתגורית שכל שלושת המספרים המרכיבים אותה יהיו באותו צבע.
שלשה פיתגורית היא שלשה של מספרים טבעיים המקיימת את השוויון , כמו למשל 3,4,5 או 5,12,13. השאלה היא, אם כך, האם אפשר לצבוע את כל המספרים הטבעיים כך שאחד מבין המספרים 3,4,5 אדום ואחד כחול; אחד מבין המספרים 5,12,13 אדום ואחד כחול; וכן הלאה.
מכיוון שיש אינסוף שלשות פיתגוריות, המשימה היא לבחור צבעים לאינסוף מספרים, באופן שיעמוד באינסוף אילוצים.
התברר שהצביעה הנדרשת אינה אפשרית.
הפותרים - מרין היולה (Marijn J.
Marek) - הראו כי אפשר לצבוע את המספרים מ-1 עד 7,824, כך שאף אחת מ-19,233 השלשות הפיתגוריות הנמצאות בטווח הזה אינה נצבעת באותו צבע; עם זאת, אי אפשר לצבוע את המספרים מ-1 עד 7,825 בלי ליצור שלשה פיתגורית באותו צבע.
כדי להוכיח זאת השאלה נוסחה כבעיית SAT-3 ב-7,825 משתנים, עם אילוץ עבור כל שלשה פיתגורית.
מספר הצביעות (או ההשמות) במקרה זה הוא , גודל שאינו מאפשר חיפוש בכוח גס.
לאחר צמצום מספר המשתנים ל-3745, הופעלה שיטה לפתרון בעיות ספיקות שידועה כ"שלש ומשול" (Cube and Conquer) שהודגמה כבר כיעילה בעבר ומאפשרת מקביליות.
הפותרים הריצו את המערכת על מחשב-על של אוניברסיטת טקסס באוסטין, שעבד על כך במשך יומיים.
לבעיות ספיקות שהתשובה עליהן היא שלילית אין בדרך כלל הוכחה קצרה לחוסר הספיקות (הבעיה היא שלמה ל-co-NP).
במקרה זה ההוכחה שנוצרה גודלה היה 200 טרה-בית של נתונים, שאותם הצליחו החוקרים לדחוס ל-68 גיגה-בית.
הפותרים פרסמו מאמר המתאר את ההוכחה ב-arXiv ב-3 במאי 2016, והציגו אותה בכנס SAT 2016 שהתקיים ביולי 2016 בבורדו שבצרפת; המאמר קיבל את פרס המאמר המצטיין בכנס.
המתמטיקאי רונלד גרהאם, שהבטיח בשנות ה-80 של המאה ה-20 פרס של 100 דולר למי שיפתור את הבעיה, העניק אותו לאחד משלושת השותפים.
מחברי המאמר שיערו באופן יותר כללי, שלא ניתן לצבוע את המספרים הטבעיים במספר סופי של צבעים באופן שאף שלשה פיתגורית לא תהיה צבועה באותו צבע.
בעיית העץ של שטיינר , שנקראת על שם יאקוב שטיינר, היא מונח המתאר קבוצה של בעיות באופטימיזציה קומבינטורית.
בעיית שטיינר בניסוחה הכללי ביותר דורשת לייצר את הקישור הקצר ביותר בין קבוצה נתונה של אובייקטים בהינתן פונקציית מרחק מוגדרת מראש.
וריאנט אחד של הבעיה, שלעיתים קרובות משמש כמונח נרדף לבעיית עץ שטיינר, הוא בעיית עץ שטיינר האוקלידית: בהינתן קבוצה של נקודות במישור, יש למצוא רשת בעלת אורך מינימלי המקשרת בין כל הנקודות.
המקור המוקדם ביותר לבעיית עץ שטיינר מופיע בהתכתבות של פייר דה פרמה (1601–1665), בה נידון המקרה הלא טריוויאלי הפשוט ביותר של בעיית שטיינר ל-n נקודות - המקרה הפרטי של n = 3. פרמה תיאר את הבעיה הזאת ב-1643 בחיבורו "שיטה לקביעת מקסימום ומינימום ומשיקים לקווים עקומים".
הפתרון הידוע המוקדם ביותר לבעיה שהציע פרמה היה בנייה גאומטרית של הפיזיקאי והמתמטיקאי האיטלקי אוונג'ליסטה טוריצ'לי (1608–1647).
הבנייה של טוריצ'לי הראתה שהנקודה שסכום מרחקיה מקודקודי המשולש מינימלי היא הנקודה בה רואים כל אחת מצלעות המשולש בזווית שווה, דהיינו 120 מעלות.
את בעיית שטיינר המוכללת הציע לראשונה קרל פרידריך גאוס (1777–1855) במכתב לחברו היינריך כריסטיאן שומאכר משנת 1836, שעסק בבעיית שטיינר במקרה של 4 נקודות.
גאוס טען שבעיה מעניינת יותר היא למצוא את הרשת הקצרה ביותר שמחברת בין כל הנקודות, במקום את הנקודה שסכום מרחקיה מכל הנקודות מינימלי.
הוא טען שבאמצעות שימוש ברשת (יותר מנקודת שטיינר אחת) ניתן לקצר את האורך הכולל של קווי הקישור שנמתחים בין הנקודות.
באותו מכתב דן גאוס בכל הטופולוגיות האפשריות של הפתרון לבעיה, והציע להשתמש בפתרון הבעיה כדי לקצר את האורך הכולל של מסילות הרכבת שיחברו בין ארבע הערים הרבורג, ברמן, הנובר ובראונשוויג.
מציאת העץ במקרה של מספר סופי של נקודות היא בעיה NP-שלמה, ונכללת ב-21 הבעיות ה-NP שלמות של קארפ.
לטענה שנקודת שטיינר של משולש ABC ממוקמת בנקודת פרמה של המשולש יש הוכחה פיזיקלית יפה.
נדמיין שולחן בצורת מנסרה שבסיסה זהה למשולש שבבעיה.
נדמיין שלושה חוטים העוברים דרך כל אחד מקודקודי הבסיס העליון של המנסרה (שצורתו כצורת משולש ABC), המחוברים ביניהם באמצעות צמה הנמצאת בפנים המשולש.
כעת נתלה על כל אחד מקצות החוטים משקולת שמסתה m.
ברור שהמערכת תתייצב בנקודה בה האנרגיה הפוטנציאלית הכוללת שלה מינימלית, וכיוון שמסת כל אחת מהמשקולות זהה, נקודה זו היא גם הנקודה בה סכום הגבהים של המשקולות מעל הקרקע מינימלי.
ניתן להראות בנקל שבמצב היציב הזה הצמה תתייצב בנקודת שטיינר של המשולש - הנקודה ממנה סכום המרחקים אל קודקודיו מינימלי.
כיוון שהמתיחות בכל אחד מהחוטים זהה ושווה למשקל המשקולת, מחשבון וקטורי פשוט ניתן להראות שהקונפיגורציה היציבה היחידה של החוטים תהיה כאשר הם נפגשים בצמה בזוויות של 120 מעלות, כלומר בנקודת פרמה של המשולש.
בעיית השרשרת התלויה של ברנולי היא בעיה בתורת התנודות שנחקרה על ידי דניאל ברנולי בשנת 1732, אשר עוסקת בתיאור התנודות הקטנות של שרשרת (או כבל מתוח) התלויה מהתקרה, ביחס למצב שיווי המשקל שלה (המתקבל כאשר השרשרת לגמרי אנכית).
חשיבותה ההיסטורית של הבעיה טמונה בכך שניסוח משוואת התנועה המכתיבה את תנודות השרשרת וחקירת הפתרונות היסודיים של המשוואה על ידי דניאל ברנולי הובילו לגילוי הראשוני של מחלקה של פונקציות מיוחדות חשובות הנקראות פונקציות בסל.
במאמרו על השרשרת התלויה דניאל ברנולי חקר מתמטית גם את בעיית התנודות של שרשרת תלויה בעלת עובי לא אחיד, שבה פילוג המשקל של השרשרת אינו קבוע אלא נתון על ידי פונקציה כלשהי .
פונקציות בסל הופיעו לאחר מכן גם בעבודתו של לאונרד אוילר על התנודות של תופים עגולים, ובעבודתו של פרידריך בסל מ-1817 על בעיות אסטרונומיות הקשורות בפתרון משוואת קפלר.
בסל סיפק את הטיפול השיטתי הראשון בתכונות הפונקציה, ומשום כך היא נושאת את שמו.
תיאור הבעיה וניסוח משוואת התנודה של השרשרת
נתונה שרשרת אנכית בעלת צפיפות מסה אורכית אחידה ואורך שמונחת בשדה כובד אחיד שגודלו , התלויה בקצה העליון שלה מהתקרה.
נמקם את ראשית הצירים בקצה התחתון של השרשרת במצבה הטבעי, ונסמן את הציר האנכי כציר ואת הציר האופקי כציר .
כעת נניח שצורת השרשרת ההתחלתית, שנתייחס אליה כאל גרף הפונקציה , אינה הישר האנכי .
אז בעיית השרשרת התלויה של ברנולי דורשת לפתור את בעיית ההתחלה עבור מצב התחלתי שרירותי של צורת השרשרת ומהירויות המקטעים האינפיניטסימליים שלה, בהנחת שיפועים קטנים של השרשרת (כלומר ש-).
במילים אחרות, לתאר את המיקום של כל מקטע של השרשרת כפונקציה של הזמן.
במסגרת המחקר השיטתי של גלים מכניים בידי מתמטיקאים ופיזיקאים רבים בתקופה הפוסט-ניוטונית, הנושא של תיאור גלים ותנודות במיתר מתוח היה אחד הנושאים "החמים" ביותר, והוביל להתקדמויות רבות כמו ניסוח משוואת הגלים ופיתוח הכלים המתמטיים המשרתים את פתרונה כגון אנליזה הרמונית וטורי פורייה.
בעיית השרשרת התלויה של ברנולי שונה באופיה ומשום שהמתיחות הנוצרת בשרשרת אינה נובעת מאיזשהו מאמץ מתיחה חיצוני המופעל על קצות המיתר, אלא כתוצאה ממשקלה העצמי, מה שגורר אי-אחידות במתיחות שנוצרת לאורכה.
נפתח כעת את משוואת התנודה עבור בעיה זו.
מהחוק הראשון של ניוטון נובע שהמתיחות כפונקציה של הקואורדינטה האנכית, , שווה למשקל השרשרת שמתחתיה, כלומר:
בפרט, המתיחות היא אפס בקצה התחתון של השרשרת ומרבית בקצה העליון שלה.
כעת, ההתנהגות המקומית של כל מקטע מצייתת לאותם כללים כמו אלו של גלים במיתר מתוח.
כלומר, הכוח הכולל הפועל על מקטע שרשרת שווה להפרש בין הכוח האופקי שמפעיל עליו המקטע שמעליו לכוח האופקי המפעיל עליו המקטע שמתחתיו (הנחת השיפועים הקטנים גוררת שהפרש הכוחות האנכיים מתאפס).
מן החוק השני של ניוטון נובע :
והצבת המתיחות מניבה את המשוואה הדיפרנציאלית החלקית:
כאשר תנאי השפה הוא .
בדומה לפתרון המתמטי עבור גלים עומדים במיתר קשור, ננחש פתרון מהצורה ("הפרדת משתנים" בין החלק המרחבי והזמני של הפתרון), ונקבל:
מכיוון שאגף שמאל תלוי בזמן בלבד ואגף ימין במקום בלבד, שוויון זה יכול להתקיים רק כאשר שני האגפים שווים לקבוע זהה, שאותו נסמן .
פתרון המשוואה הדיפרנציאלית עבור החלק הזמני נותן , בעוד שהפתרון עבור החלק המרחבי מקיים את המשוואה הדיפרנציאלית הרגילה
אופני התנודה העצמיים, המתוארים מתמטית על ידי סדרת הפונקציות העצמיות של משוואה דיפרנציאלית רגילה זאת, תואמים לתנודות הרמוניות אופקיות של כל אחד ממקטעי השרשרת בתדירות עצמית , כאשר משרעת התנודה של כל מקטע תלויה במיקומו על השרשרת באופן כזה שמעטפת התנודות של כל המקטעים היא פונקציית בסל מסדר אפס:
כאשר התדירויות העצמיות "המותרות" נקבעות על ידי תנאי השפה, שכן צריך להתקיים .
הפתרון הכללי ביותר של בעיית ההתחלה עבור השרשרת התלויה הוא סופרפוזיציה של פתרונות עצמיים.
בשעשועי מתמטיקה, בעיית לנגלי היא חידה במסגרתה צריך להסיק באופן גאומטרי סינתטי זווית מסוימת בתרשים גאומטרי מזוויות נתונות אחרות בתרשים.
החידה הוצעה על ידי אדוארד מאן לנגלי במגזין המתמטי The Mathematical Gazette, בשנת 1922.
בגרסתה המקורית הבעיה הוצגה באופן הבא:
הוא משולש שווה-שוקיים עם זוויות בסיס .
נטוי ביחס ל- בזווית וחותך את בנקודה .
מכיוון שניתן להסיק את הזווית המבוקשת בקלות יחסית באמצעות תהליך חישובי המתבסס על משפטים טריגונומטריים, עיקר הקושי בפתרון חידת לנגלי הוא במתן פתרון סינתטי בעל פשטות מרבית, שאינו עושה שימוש בטריגונומטריה.
הבעיה של חישוב הזווית היא דוגמה סטנדרטית לבעיית הנסן בגיאודזיה.
חישובים טריגונומטריים יכולים להראות שזווית היא בכל רמת דיוק שנרצה, אך מכיוון שלמכשיר החישוב דיוק סופי, הם עדיין מותירים ספק לגבי ערכה המדויק.
הוכחה ישירה באמצעים גאומטריים קלאסיים בלבד פותחה בידי ג'יימס מרסר ב-1923. הפתרון שלו מערב בניית עזר של קו ישר נוסף, ואז שימוש חוזר בעובדה שסכום הזוויות במשולש הוא 180° כדי להראות שכמה מהמשולשים המשורטטים הם כולם שווי שוקיים.
שרטטו קו ישר בזווית ביחס לבסיס החותך את בנקודה ושרטטו את .
מכיוון ש- ו- אז ומשולש הוא גם שווה-שוקיים עם .
מכיוון ש- ו- אז ומשולש הוא שווה-שוקיים עם .
מכיוון ש- ו- אז משולש הוא שווה-צלעות.
מכיוון ש- ו- אז ולכן משולש הוא שווה-שוקיים עם .
לפיכך כל הקטעים האדומים באיור שווים.
כיוון ש-, משולש הוא שווה-שוקיים עם .
פתרונות סינתטיים רבים אחרים קיימים.
רשימת Cut the Knot מונה כתריסר פתרונות שונים ומספר גרסאות חלופיות לבעיה.
בעיית לנגלי זכתה לכינוי "בעיית הזוויות המיוחדות", משום שרק בעבור צירופים מיוחדים מסוימים של זוויות זה אפשרי בעבור כל הזוויות בתרשים להיות כפולה רציונלית של פאי.
בדומה לכך, מרובע כמו BCEF ייקרא מרובע מיוחד כאשר הזוויות בין אלכסוניו וצלעותיו הן כולן זוויות רציונליות, כלומר זוויות המהוות מספר רציונלי של מעלות או כל יחידת זווית אחרת שעבורה מעגל שלם נמדד במספר יחידות רציונלי.
מספר מרובעים מיוחדים מעבר למרובע המקורי של לנגלי נבנו במהלך השנים.
בגאומטריה, בעיית חובק-המפיות (napkin ring problem) קשורה בנפח של "רצועה" בגובה מוגדר סביב כדור, כלומר החלק שנותר לאחר קדוח חור בצורת גליל עגול דרך מרכז הכדור.
מפתיע כי נפח זה אינו תלוי ברדיוס הכדור המקורי אלא רק בגובה הרצועה המתקבלת.
הבעיה נקראת כך כי לאחר הסרת גליל מהכדור, הרצועה הנותרת דומה לצורה של חובק מפיות.
נניח שהציר של גליל עגול ימני עובר דרך מרכז כדור ברדיוס ו- מייצג את גובה הגליל שנמצא בתוך הכדור.
הרצועה (חובק המפיות) הוא החלק של הכדור שנמצא מחוץ לגליל.
נפח הרצועה תלויה אבל לא ב :
כאשר הרדיוס של הכדור קטן, גם קוטר הגליל קטן על מנת ש לא ישתנה.
הרצועה נעשית עבה יותר, מה שמגדיל את נפחה.
אך ההיקף של הרצועה קטן, מה שמקטין את נפחה.
שני האפקטים הללו בדיוק מבטלים זה את זה.
במקרה הקיצוני של הכדור הקטן ביותר האפשרי, הגליל נעלם (הרדיוס שלו הופך לאפס) והגובה שווה לקוטר הכדור.
במקרה זה נפח הרצועה הוא נפח הכדור כולו, התואם את הנוסחה שניתנה לעיל.
נסמן ב- את רדיוס הכדור וב- את אורך הגליל .
לפי משפט פיתגורס רדיוס הגליל הוא
ורדיוס החתך האופקי של הכדור בגובה מעל "קו המשווה" הוא
חתך הרצועה עם מישור בגובה הוא האזור בתוך מעגל הרדיוס הגדול שנתון על ידי (2) ומחוץ למעגל הקטן יותר של הרדיוס שנתון על ידי (1).
שטח החתך הוא אם כן שטח המעגל הגדול פחות שטח המעגל הקטן יותר:
הרדיוס R אינו מופיע בביטוי.
לכן, שטח החתך האופקי בגובה אינו תלוי , כל עוד .
נפח הרצועה הכולל הוא אם כן
זהו יישום של עיקרון קאוואליירי: נפחים עם חתכים מתאימים בגודל שווה - שווים.
ואכן, שטחי החתכים זהים לשטחי החתכים של כדור ברדיוס .
בעיית שחמט היא חידה שמתנהלת לפי כללי משחק השחמט, שבה מוצגת עמדת שחמט מסוימת על לוח השחמט, ועל הפותר להגיע למצב כלשהו (לדוגמה: מט או יתרון חומרי).
בחלק מהחידות יש הגבלות של כללים מיוחדים, בהתאם לסוג הבעיה; לדוגמה: יש בעיות שיש בהן הגבלה על מספר המסעים.
אדם העוסק בפתרון או בחיבור בעיות שחמט באופן מקצועי נקרא פרובלמאי.
בעיות שחמט לרוב יצייתו לכללי המשחק, אך יש כאלה שחורגות מהם.
למרות זאת, הן שומרות על החוקים הבסיסיים ועוסקות במצבים, ובכך הן נבדלות מחידות שחמט, שבהן משתמשים בלוח ובכלים אך לא במצבים.
בעיות שחמט נחשבות כמפתחות את החשיבה הלוגית ואת היכולת במשחק השחמט, אפילו כאלה שמטרתן הפוכה ממטרת משחק השחמט (לדוגמה: מט לדעת), ואף על פי שהמצבים שמוצגים בבעיות שחמט מורכבים ובדרך כלל לא יגיעו במשחק רגיל.
בעיות שחמט נחשבות כתחום עצמאי במשחק השחמט.
יש ספרות ענפה בנושא, ומתקיימות אליפויות קומפוזיציה (חיבור בעיות) ופתרון בעיות.
שחקני שחמט רבים עוסקים בהן.
יש המתמקדים בבעיות שחמט, ועוסקים פחות בשחמט רגיל.
מט בשני מסעים (אלן ווייט 1920).
מט במספר מסעים - הלבן מתחיל ועליו להנחית מט על השחור במספר מסעים נתון, כאשר הוא יוכל להנחית מט ללא תלות מה יעשה השחור.
מט בשני מסעים - (מכונה גם דו-מסעית) לבן מבצע מהלך, כך שבתור הבא יוכל להנחית מט.
חידות אלה הן הפופולריות ביותר בגלל פשטותן.
מט עזר - השחור מתחיל (בדרך כלל) ומסייע ללבן להנחית לשחור מט.
פט עזר - השחור מסייע ללבן להגיע למצב של פט.
מט לדעת - הלבן מתחיל וכופה על השחור, נגד רצונו, להנחית ללבן מט.
מט רפלקס - בעיית מט לדעת, שבה מי שיכול להנחית מט חייב להנחית אותו.
בעיה סדרתית - בעיה שבה אחד מהצדדים משחק כמה תורות ברצף.
סיום - חידות "מציאותיות" ללא הגבלה על מספר המסעים.
בעיות אלה מתחלקות לשני סוגים עיקריים: