בעיית שני הצבאות

מתוך ויקיפדיה, האנציקלופדיה החופשית
הצבאות A1, A2 צרים על העיר B

בעיית שני הצבאות (נקראת גם בעיית ההתקפה המתואמת או בעיית שני הגנרלים) היא ניסוי מחשבתי המציג את הבעייתיות בתקשורת על גבי ערוץ לא אמין.

הבעיה עוסקת בשני צבאות הצרים על עיר. העיר חזקה מכל אחד מהצבאות בנפרד, אך לא משניהם גם יחד. לכן, על מנת לנצח, על שני הצבאות לתקוף את העיר בעת ובעונה אחת. שני הצבאות מסוגלים לתקשר באמצעות שליחים בלבד, אך אלה עשויים להיתפס על ידי שומרי העיר, והצבא ששלח אותם אינו מסוגל לדעת אם הודעתו הגיעה ליעדה.

ניתן להוכיח שאין כל שיטה אשר תאפשר לאחד הצבאות לצאת להתקפה בוודאות מוחלטת שהצבא השני יצא להתקפה בו זמנית.

קישורים חיצוניים[עריכת קוד מקור | עריכה]