תודיחל תורוקמה תמישרל
תודיחה תמישרל

המרפ לע תויצאירו

המרפ לש ןטקה טפשמה

לכלו p ינושאר רפסמ לכל :האבה הנעטה תא המרפ הלעה 1640 תנשב חלשש בתכמב
,וכרדכ ,המרפ ךא ,וז הנעט חיכוהל השק אל .p-ב קלחתמ np-n רפסמה ,םלש n
םשל התכז הנעטה .רליואו ץינבייל וקפיס החכוהה תאו ,ארוקל החכוהה תא ריתוה
:אבה גולאידה תא חנעפל ךל עייסת איהו ,"המרפ לש ןטקה טפשמה"

."םיינושאר םירפסמ ףוסניא שי"
"?רתוי שדח והשמ ךל שי .הז תא חיכוה סדילקוא רבכ ,ןכ"
".הז ינושארב קלחתמה תויעישת ולוכש רפסמ םיאתמ םיינושארה ףוסניאמ דחא לכל"
ולוכש רפסמ ןיאו ,2-ב קלחתמש תויעישת ולוכש רפסמ ןיאש עדוי דלי לכ !תמזגה"
."5-ב קלחתמש תויעישת
םיאתמ ,5 וניאו 2 וניאש ,p ינושאר רפסמ לכל :ירבדב קיידא ,יתמזגה ,המשאב הדומ"
."p-ב קלחתמה תויעישת ולוכש רפסמ
"?הז תא חיכות ךיא"
."ךל ריאשמ ינא וזה היעבה תא ,המרפל המודב"

,p-ב קלחתמ 10p-10 :םייקתמ p ינושאר רפסמ לכל ,"המרפ לש ןטקה טפשמ"-ל םאתהב
,10p-1-1 רפסמהש ךכמ עבונ ,5 וניאו 2 וניא p רשאכ .p-ב קלחתמ 10(10p-1-1) רמולכ
.p-ב קלחתמ ,תויעישת p-1 ןב רפסמ אוהש


הנטקה הקזחהו ןטקה טפשמה

תודיחיה תרפס רמולכ ,תודיחיה תרפס תא הנשמ הניא 10 תפסוה ,n םלש רפסמ לכל
10 ךא ,'וכו 30 וא 20 ףיסונ רשאכ םג תמייקתמ וז הנוכת .n לש וזל הווש האצותה לש   
.וז הנוכת לעב (1-מ לודגה) רתויב ןטקה רפסמה אוה   
תרפס רמולכ ,תודיחיה תרפס תא הנשמ הניא 11-ב ותלפכה ,n םלש רפסמ לכל
וא 21-ב ליפכנ רשאכ םג תמייקתמ וז הנוכת .n לש וזל הווש האצותה לש תודיחיה   
.וז הנוכת לעב (1-מ לודגה) רתויב ןטקה רפסמה אוה 11 ךא ,'וכו 31-ב   
,1-מ הלודגה ,רתויב הנטקה הקזחה תא אצמ "המרפ לש ןטקה טפשמה" תועצמאב
תרפס ,וז הקזחב הלענש n םלש רפסמ לכלש תמייקמ איה רמולכ ,וז הנוכת תלעב   
.n לש וזל הווש האצותה לש תודיחיה   

np-n םאש םושמ ,הדיחבש יאנתה לע הנעי 10-ב קלחתמ np-n ורובעש p ינושאר רפסמ
תרפסל הווש np לש תודיחיה תרפס ןכלו ,0 איה ולש תודיחיה תרפס זא ,10-ב קלחתמ
.n לש תודיחיה

,ינושאר וניא 10 ירהש ,10-ל הוושש p תודוא רבד רמוא וניא "המרפ לש ןטקה טפשמה"
"המרפ לש ןטקה טפשמה" יפלש םושמ ,ןוכנה ןוויכב דעצכ הארנ 5-ל הוושש p ךא
:חיכוהל לק תאז .2-ב םג קלחתמ n5-n רפסמהש חיכוהל ונילע תעכ .5-ב קלחתמ n5-n
.יגוז n5-n ןכלו יגוז-יא n5 זא יגוז-יא n םאו ,יגוז n5-n םג ןכלו יגוז n5 זא יגוז n םא

5-ש תוארהל רתונ .n לש תודיחיה תרפסל הווש n5 לש תודיחיה תרפס n לכלש ונארה
,היינשה הקזחה תקידב תועצמאב עיגנ ךכל .תאז תמייקמה רתויב הנטקה הקזחה איה
.2-מ הנוש תודיחיה תרפס ןהבש ,2 לש תיעיברהו תישילשה


המרפ לע היצאירו

.xn+yn=zn :הלש היצאירוול רבעו x2+y2=z2 סרוגתיפ לש האוושמהמ אצי המרפ
.המרפ לש האוושמה לע תויצאירו רוציל וסינו המרפ תובקעב וכלה ,רליואב לחה ,םיבר
Godel, Escher, Bach: An Eternal Golden Braid ורפסב גיצמ רטטשפוה סלגאד
:האבה היצאירווה תא
?םייבויח םימלשב ןורתפ nx+ny=nz האוושמל שי n לש םיכרע הזיאל

.1+1=1 ןויוושה תא ןתי ןורתפ לכש םושמ ,ןורתפ ןיא האוושמל n=1 רשאכ
.23+23=24 לשמל ,z=x+1 ,x=y םהבש ,תונורתפ ףוסניא האוושמל שי n=2 רשאכ
תוטיש לע תרוכזת הליחת ךא ,ןורתפ ןיא האוושמלש הלילשה ךרדב חיכונ n>2 רשאכ
:הריפס
.9 דע 0-מ ,תורפס רשע ובש ,10 סיסב יפל הריפס תטישב איה תלבוקמה הקיטמתיראה
קר הבו ,2 אוה הסיסבש הריפס תטישב רמולכ ,תיראניב הקיטמתיראב לעופ בשחמה
הבש ,תילמיצד-הסקה הריפס תטיש םיבשחמה םלועב תלבוקמ דוע .1-ו ,0 תורפס יתש
.תורפס 16

ונימימו 1 ותרוצש רפסמ איה סיסבה לש 1-מ הלודג המלש הקזח ,הריפס תטיש לכב
.103 = 1000 :המגוד .םידחא םיספא

םושרנ .nx+ny=nz םימייקמש x, y, z, n םימייק רמולכ ,ןורתפ שי האוושמלש חיננ
:םיירשפא םיבצמ השולש קודבנו ,n אוה הסיסבש הריפס תטישב ןורתפה תא
nx+ny םוכסה ןכלו ,םיספא x ונימימו 1 ותרוצש רפסמ אוה nx=ny זא ,x=y םא
,n לש הקזח וניא ותרוצ וזש רפסמ ךא ,םיספא x ונימימו 2 ותרוצש רפסמ אוה   
.n לש הקזח אוה nz רפסמהש ךכל הריתסב   
1 םנימימש םיספא x-y-1 ונימימו 1 ותרוצש רפסמ אוה nx+ny םוכסה זא ,x>y םא
רפסמהש ךכל הריתסב ,n לש הקזח וניא ותרוצ וזש רפסמ ,בוש .םיספא y ונימימו   
.n לש הקזח אוה nz   
.x>y רשאכ וילא ונעגהש הזל המוד בצמה ,x<y םא

.n>2 רשאכ ןורתפ האוושמל ןיא ןכלו ,הריתסל הליבומ ןורתפ שי האוושמלש החנהה


סרפ ךל הכחמ ססקטב

הרעשהה תא 1997 תנשב הלעה ,ססקט ,סאלאדמ יאקנב ,(Andrew Beal) ליב ורדנא
:המרפ לש ןורחאה טפשמה תובקעב ,האבה

a,b,c -לו x,y,z>2 רשאכ םייבויח םימלשב ןורתפ ןיא ax+by=cz האוושמלש הארה
.a,b,c תא קלחמש 1-מ לודג רפסמ ןיא רמולכ ,ףתושמ םרוג ןיא

:לשמל ,ןורתפ האוושמל שי 2 וא 1 איה תוקזחהמ תחא רשאכ

11 + 23 = 32

25 + 72 = 34

:לשמל ,ןורתפ האוושמל שי ףתושמ םרוג שי a,b,c -ל רשאכ םג

25 + 25 = 43

ותנעט םג .x=y=z ובש ,ליב תרעשה לש יטרפ הרקמ הווהמ המרפ לש ןורחאה טפשמה
הדיחב ונחכוה התואו ליב תרעשה ינפל הנש 18 המסרופש ,רטטשפוה סלגאד לש
.ליב תרעשה לש יטרפ הרקמ איה ,תמדוקה

ןתניי סרפה .רלוד 50,000 תעכ והבוגש ,סרפ לע הזרכהב ליב הוויל ותרעשה תא
,ךידיב החכוהה םא .תידגנ המגוד איבי וא הרעשהה תונוכנל החכוה קפסיש ןושארל
:רתאב העיפומ החכוהה חולשמל תקיודמה תבותכה
The Beal Conjecture and Prize



?רנוילימ תויהל הצור ימ

רתויב תוינדרוטה תויעבה תחא תא הרתפ המרפ לש ןורחאה טפשמל החכוה תאיצמ
גיצה 1900 תנשב .ןנורתפ תא תושרודו תוצצ תושדח תויעב ךא ,הקיטמתמה תודלותב
ךלהמב םיבר םיאקיטמתמ וקיסעהש ,תויזכרמ תויטמתמ תויעב שולשו םירשע טרבליה
ןוכמ" זירכה 2000 יאמב 24-ב .ןהירתופל יפסכ סרפ חטבוה אלש ףא ,םירשעה האמה
לש סרפב רתופה תא הכזמ ןהמ תחא לכ ןורתפש תויעב עבש לע "הקיטמתמל יילק
.Millennium Prize Problems רתאב עיפומ תויעבה לש טרופמ רואת .רלוד ןוילימ

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

העודיו ,הרקנאופ ירנא יתפרצה יאקיטמתמה די-לע 1904 תנשב התלעוהש ,תויעבהמ תחאל
םדוק ןורתפ) הקידב הנועט הנדוע ותנוכנש ,ןורתפ אצמנ ,"הרקנאופ תרעשה" םשב זאמ
.(יוגש אצמנ וז היעבל עצוהש

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


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

הסניש בשחמל התוא ןתינ םא םגו ,וז הדיח רותפל ןתינ היעטו יוסינ לש המ ןמז רחאל
אל ןמז רחאל ןורתפה גשוי ,םיירשפאה םירודיסה לכ תקידב תועצמאב התוא רותפל
םינש תואמל בשחמה קקדזי 7X7-ל 3X3-מ םינטקה םיעובירה רפסמ תא לידגנ םא .בר
רפסמ רשאכ םג ריבס ןמזב וז הדיח רותפל ךרד שי םאה .ןורתפל עיגהל תנמ-לע
.רלוד ןוילימב ךתוא הכזת וז הלאשל האלמ הבושת ?לדג םיעובירה

ביבחה קחשמה איה NP-ב תומלשה תויעבה תמישרב איה ףא תללכנה תפסונ העודי היעב
התא םא םג .Windows הלעפהה תכרעמ םע דחי אבש ,(Minesweeper) "םישקומה הלוש"
תקסוע הז קחשמב הרושקה היעבה .סרפה תא שורדל ץורת לא ,הז קחשמב דימת חצנמ
תושעל ןתינ םאה הלאשבו ,םילדגו םיכלוה תוחול יבג-לע קחשמה תא חתנל תלוכיב
.ריבס ןמזב הז חותינ


© יש דודל תורומש תויוכזה לכ 1998



תודיחל תורוקמה תמישרל
תודיחה תמישרל