בעיית המטבעות

אני רוצה להציג הפעם בעיה שמתאימה בול לבלוג: היא קלה לניסוח, מעניינת ובעלת פתרון שלא דורש מתמטיקה עמוקה בכלל, כך שהוא ניתן להבנה על ידי קוראים חסרי רקע במתמטיקה (אבל שכן מוכנים להשקיע מאמץ בנסיון להבין); מצד שני, ההצגה והפתרון שלה נותנים לנו הזדמנות להרגיש בדיוק מה קורה במתמטיקה - ברמת הניסוחים הפורמליים שמקלים עלינו, ושיטות ההוכחה. בקיצור, אם מעולם לא נתקלתם במתמטיקה, נסו לקרוא את הפוסט הזה!

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

נתחיל מדוגמאות קונקרטיות. בישראל כיום יש לנו מטבעות עבור 10 אגורות, 50 אגורות, 1 שקל, 2 שקלים, 5 שקלים, 10 שקלים, 20 שקלים, 50 שקלים, 100 שקלים ו-200 שקלים. המילה “מטבעות” קצת מטעה, כמובן, כי 20,50,100,200 הם סכומים שבאים בשטרות, לא במטבעות; אבל אני משתמש במילה “מטבעות” כדי לתאר כל סוג של כסף מזומן. כמו כן, אין לי כוח לאגורות אז בואו נשכח מקיומן ונדבר רק על סכומים שהם מספר שלם של שקלים. עכשיו, איך אפשר לייצג 12 ש”ח? הנה כמה דרכים: אפשר להשתמש ב-12 מטבעות של 1 ש”ח; אפשר להשתמש ב-6 מטבעות של 2 ש”ח; אפשר להשתמש ב-5 מטבעות של 2 ש”ח ובשני מטבעות של 1 ש”ח; אפשר להשתמש במטבע אחד של 10 ש”ח ומטבע אחד של 2 ש”ח, ועוד ועוד. אנחנו רואים שגם עבור סכום כסף קטן יחסית יש לו המון ייצוגים שונים. השאלה היא - מה הייצוג האופטימלי?

אופטימליות יכולה להימדד בכמה דרכים, אבל הדרך הכי מתבקשת היא פשוט כמה שפחות מטבעות (אני מתעלם כאן מעניינים של משקל וגודל המטבעות שאולי משפיעים על מה שאנחנו נתפוס כ”אופטימלי”). לכן ההצגה של 12 בתור 10 ועוד 2 היא האופטימלית, כי היא משתמשת בשני מטבעות בלבד.

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

חשבתם? קרוב לודאי שהחלוקה שחשבתם עליה היא 20 ועוד 10 ועוד 1. זו חלוקה מאוד טבעית, שנובעת משיטת חלוקה שאוהבים לקרוא לה “חמדנית”. בשיטה החמדנית, בכל רגע נתון בוחרים בדבר “הכי טוב” שנראה שאפשר לעשות כרגע. ספציפית אצלנו זה אומר שאנחנו בוחרים את המטבע בעל הערך הגבוה ביותר שעדיין לא עובר את הסכום שאנחנו רוצים לייצג כרגע, ואז מנסים לייצג את מה שנשאר. במקרה של 31 התחלנו מ-20 כי המטבע הבא (50) כבר גדול מדי. נותר לנו לייצג את 11, ולכן המטבע הבא היה 10, וזה שאחריו היה 1. בדומה, עבור 76 נקבל בשיטה החמדנית את 50 ואז 20 ואז 5 ואז 1.

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

למרבה המזל, בבריטניה הייתה נהוגה בעבר שיטת מטבעות הזויה לחלוטין, שבה התכונה הנחמדה הזו לא התקיימה. במערכת המטבעות הזו ערכי המטבעות היו 1,3,6,12,24,30,60,240 (יחידת המטבע הבסיסית היא פני). מה האלגוריתם החמדני יתן עבור 48 במערכת המטבעות הזו? קל לראות שאת החלוקה 30+12+6, שכוללת 3 מטבעות. לעומת זאת, החלוקה 24+24 כוללת רק 2 מטבעות ולכן עדיפה. מסקנה: קיימות מערכות של מטבעות שבהן החלוקה החמדנית אינה אופטימלית.

מכאן נובעות שתי שאלות הכרעה אלגוריתמיות:

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

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

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

מה שנכון הוא שאפשר לנסות לתקוף את בעיה 1 בעזרת בעיה 2: ראשית כל נבדוק אם מערכת המטבעות שלנו היא כזו שבה חלוקה חמדנית היא תמיד אופטימלית. אם זה אכן המצב, אז התשובה לשאלה ב-1 היא תמיד “כן” בלי קשר לשאלה מה הסכום שלנו; כלומר, במקרה כזה גם שאלה 1 היא קלה. אבל אם התשובה ל-2 הייתה “לא” אז אין לנו מושג איך לענות ל-1; ייתכן שהחלוקה החמדנית לא עובדת עבור הסכום שלנו וייתכן שהיא כן. כלומר, זה שאנחנו יודעים איך לפתור את 2 ביעילות לא עזר לנו לפתור את 1.

מה שאני רוצה לעשות בפוסט הזה הוא שלושה דברים: ראשית, להראות איך מפרמלים מתמטית את הבעיות הללו; שנית, להסביר מה האלגוריתם היעיל שפותר את 2; ולבסוף, לומר משהו על איך מראים ש-1 קשה. רק עבור ה”לבסוף” אצטרך לדרוש ידע מוקדם כלשהו, למרות שתוכלו פשוט להאמין לכמה הצהרות שאזרוק שם ולוותר על הידע המוקדם הזה.

בואו נעבור לניסוחים פורמליים. את מערכת המטבעות נסמן באות \( C \). מערכת כזו מאופיינת על ידי סדרה של מספרים טבעיים - ערכי המטבעות האפשריים. נסדר אותם מהגדול לקטן, כלומר \( C=\left(c_{1},c_{2},\dots,c_{n}\right) \) כאשר \( c_{1}>c_{2}>\dots>c_{n} \). כמו כן נניח ש-\( c_{n}=1 \), כי אחרת מערכת המטבעות שלנו לא שלמה ולא יכולה לייצג חלק מהסכומים (לפחות את 1). אז למשל, במערכת הישראלית יש לנו \( C=\left(200,100,50,20,10,5,2,1\right) \) (ו-\( n=8 \)). למי שלא מכיר - סדרה כזו של איברים נקראת לעתים קרובות וקטור והאיברים האינדיבידואלים בוקטור מכונים כניסות.

עכשיו, ייצוג של סכום כלשהו במערכת \( C \) הוא בעצם סדרה של \( n \) מספרים טבעיים, שאומרים “כמה מכל סוג מטבע אנחנו לוקחים”. כך למשל \( V=\left(0,0,1,0,1,0,1,0\right) \) הוא ייצוג של 50+10+2, כלומר של 62. עכשיו נכניס לתמונה הוקוס-פוקוס של סימון מתמטי סטנדרטי: אם \( \left(a_{1},\dots,a_{n}\right) \) ו-\( \left(b_{1},\dots,b_{n}\right) \) הם שני וקטורים, אז המכפלה הסקלרית שלהם מתקבלת מכפל של איברים באותו מקום בשני הוקטורים וחיבור של כולם. נכון שבכלל לא הבנתם מה אמרתי כרגע? זה כי ניסוחים טקסטואליים הם מסורבלים ונוסחאות קלות יותר להבנה:

\( \left(a_{1},\dots,a_{n}\right)\cdot\left(b_{1},\dots,b_{n}\right)=\sum_{i=1}^{n}a_{i}b_{i}=a_{1}b_{1}+a_{2}b_{2}+\dots+a_{n}b_{n} \)

סימן ה-\( \sum \) הוא סימון מקוצר לסכימה שמקובל במתמטיקה; עבור מי שלא מכיר אותו כתבתי את הסכום יותר במפורש מימינו.

כעת, חמושים בסימן המכפלה הסקלרית, קל לנו להמשיך: אם \( C \) היא מערכת המטבעות שלנו ו-\( V \) הוא וקטור של טבעיים, אז המספר ש-\( V \) מייצג במערכת \( C \) הוא פשוט \( C\cdot V \). כמו כן, אם נסתכל על \( V\cdot\left(1,1,\dots,1\right) \) נקבל את מספר המטבעות שבהן \( V \) משתמש (זה בעצם סכום כל הכניסות של \( V \)). נשתמש בסימון המקוצר \( \left|V\right|=V\cdot\left(1,1,\dots,1\right) \) ונאמר ש-\( \left|V\right| \) הוא המשקל של \( V \).

כעת אנחנו רוצים לתאר את הוקטור שהוא הייצוג הטוב ביותר של מספר \( x \) כלשהו במערכת המטבעות \( C \). ברור שזה צריך להיות וקטור \( V \) שמקיים \( C\cdot V=x \), אבל אי אפשר סתם לומר “בואו ניקח מבין כל ה-\( V \) האפשריים את זה בעל המשקל המינימלי”, כי אולי יש כמה וקטורים שונים בעלי משקל מינימלי שכזה. למשל, במערכת המוזרה של הבריטים אפשר לייצג את 36 בתור 30+6 או בתור 24+12 - שני ייצוגים מגודל 2, ואין ייצוג מגודל 1 כי אין מטבע של 36. אז צריך לבחור בצורה כלשהי מי מבין שני הייצוגים הללו הוא “טוב יותר”, והבחירה שלנו היא להעיף כמה שיותר מטבעות גדולים. כמקודם, גם כאן הפורמליזם יאפשר לי להסביר את הכוונה שלי יותר טוב מאשר מילים.

למי שמכיר, מה שאנחנו עושים הוא קובעים סדר לקסיקוגרפי על הוקטורים \( V \) האפשריים באופן הטבעי. למי שלא מכיר, הנה מה שזה אומר. ראשית, בואו ניזכר איך מילים מסודרות במילון (בהנחה שמישהו עדיין זוכר איך מילים מסודרות במילון…): ראשית כל מופיעות כל המילים שמתחילות באות א’, אחריהן אלו שמתחילות באות ב’ וכדומה. כלומר, משווים מילים על פי האות הראשונה שלהן. אם היא שונה, אז באה קודם מי שהאות הראשונה שלה באה קודם. ומה עם מילים שבהן האות הראשונה שווה? עוברים לאות השניה, וכדומה.

ניקח את אותו רעיון עבור וקטורים. נסמן \( U<V \) אם קיים \( 1\le i\le n \) כך ש-\( u_{j}=v_{j} \) לכל \( j<i \) וכמו כן \( u_{i}<v_{i} \). למשל, \( \left(1,100,500\right)<\left(2,0,3\right) \). כעת אפשר לומר על וקטור כלשהו \( V \) שהוא מקסימלי בקבוצת וקטורים אם לכל וקטור \( U \) שונה ממנו בקבוצה מתקיים \( U<V \).

עכשיו אפשר לומר בדיוק מה אנחנו רוצים: בהינתן מערכת מטבעות \( C \) וערך \( x \) כלשהו, אני מסמן ב-\( M\left(x\right) \) (\( M \) מלשון Minimal) וקטור \( V \) שנבחר כך: ראשית אני מסתכל על כל הוקטורים \( U \) המקיימים \( C\cdot U=x \). שנית, מביניהם אני מסתכל על כל אלו שעבורם \( \left|U\right| \) הוא מינימלי; ולבסוף, מבין מי שנשארו אני לוקח את זה שהוא מקסימלי בסדר הלקסיקוגרפי להיות ה-\( V \) שלי. אפשר לכתוב את זה פורמלית באופן הבא:

\( V=\max\left(\arg\min_{\left|U\right|}\left\{ U\ |\ C\cdot U=x\right\} \right) \).

הכתיב הפורמלי כאן הוא לטעמי מסובך מדי ואין ממש הכרח להשתמש בו - ברור מה אני רוצה גם מהניסוח המילולי. עם זאת, יש כאן מוקש נפוץ למדי במתמטיקה שצריך להיזהר איתו. אני מגדיר כאן אובייקט כלשהו, אבל בכלל לא מובטח לי שהוא קיים. הסכנה במקרה הספציפי שלנו היא שאף אחד לא מבטיח לי אוטומטית שקבוצת “כל הוקטורים \( U \) המקיימים \( C\cdot U=x \)” אינה ריקה. במקרה שלנו, מכיוון שאמרנו שהמטבע 1 תמיד יהיה במערכת המטבעות שלנו, תמיד יש וקטור כזה - \( U=\left(0,0,\dots,0,x\right) \), ולכן ההגדרה שלי טובה (שימו לב שהוקטור הזה הוא הקטן ביותר בסדר הלקסיקוגרפי, וש-\( \left|U\right| \) יהיה הגדול ביותר מבין כל המשקלים של וקטורים שמייצגים את \( w \)).

אם כן, \( M\left(x\right) \) הוא הייצוג האופטימלי של \( x \). עדיין נותר להגדיר את הייצוג החמדני, אבל זה קל - אנחנו פשוט מוותרים על דרישת המינימום של המשקל. דהיינו, אגדיר \( G\left(x\right)=\max\left\{ U\ |\ C\cdot U=x\right\} \) (כאן \( G \) הוא מלשון Greedy - חמדני). למה האיבר המקסימלי לקסיקוגרפית מבין אלו שמייצגים את \( x \) מתאים לייצוג החמדני? כי מה זה אומר, שהוא ראשון לקסיקוגרפית? ראשית, שהכניסה הראשונה (שמייצגת את המטבע הכי גדול) היא הכי גדולה שרק אפשר כך שעדיין נייצג את \( x \); ואחר כך הכניסה השניה היא הגדולה ביותר שרק אפשר, בהינתן הערך של הכניסה הראשונה, וכן הלאה. זה זמן טוב לעצור ולוודא שאתם מבינים אותי (ואת כל הסימונים שהיו עד כה). אם איבדתם אותי, נסו לקרוא שוב, או לנסות ולהמציא את ההגדרות מחדש בעצמכם; אין טעם להמשיך לקרוא בלי להרגיש בנוח עם מה שהלך עד כה.

כעת אפשר לנסח מתמטית את מה שאנחנו רוצים. נאמר שמערכת המטבעות \( C \) היא קנונית אם \( M\left(x\right)=G\left(x\right) \) לכל \( x \) טבעי. שתי הבעיות שלנו, אם כן, הן הבעיות הבאות:

1. בהינתן \( C,x \), האם \( M_{C}\left(x\right)=G_{C}\left(x\right) \)?
2. בהינתן \( C \), האם \( M_{C}\left(x\right)=G_{C}\left(x\right) \) לכל \( x \)?

הוספתי את \( C \) ל-\( M,G \) למטה כדי לציין שהפונקציות הללו תלויות במערכת המטבעות \( C \) שלנו. בדרך כלל זה מובן מאליו ולכן אני לא טורח לכתוב את זה במפורש, אבל בניסוח הפורמלי של הבעיות שאנחנו רוצים לפתור זה נראה לי מתאים.

עכשיו בואו נעבור לפתרון הבעיה שאנחנו יודעים לפתור - בעיה 2. הרעיון הוא שבהינתן מערכת המטבעות \( C \), אם היא לא קנונית אז יש דוגמאות נגדיות לקנוניות שלה - כל מני \( x \)-ים שמקיימים \( M\left(x\right)\ne G\left(x\right) \). מביניהם, נסמן ב-\( w \) את הדוגמה הנגדית הקטנה ביותר. הפתרון שלנו יתבסס על כך ש-\( w \) יכול להיות רק אחד מבין לכל היותר מספר לא גדול של ערכים שונים שאפשר לחשב מתוך \( C \) - מספר שלא אתן במדויק אבל הוא לא גדול מ-\( n^{2} \) (כאשר \( n \), כזכור, הוא מספר המטבעות ב-\( C \) - ה”אורך” של הוקטור \( C \)). יותר מכך - עבור כל ה-\( w \)-ים הפוטנציאליים הללו, אנחנו יודעים בדיוק מהו \( ,M\left(w\right) \) ולכן כל מה שנותר לנו לעשות הוא לחשב עבורם את \( G\left(w\right) \) (זה מהיר) ולבדוק אם \( G\left(w\right)\ne M\left(w\right) \). אם כן - סיימנו; הוכחנו ש-\( C \) אינה קנונית. אם לכל \( n^{2} \) המועמדים שבדקנו התקיים \( G\left(w\right)=M\left(w\right) \) אנחנו יכולים לעצור ובלב שקט לומר ש-\( C \) קנונית.

אבל איך נראים המועמדים? ובכן, אני אתן עכשיו את הניסוח המדויק של המשפט שנותן לנו אותם. בהתחלה ממש לא יהיה ברור למה שהמשפט הזה יהיה נכון - מן הסתם מה שאעשה בהמשך יהיה להוכיח אותו. המשפט הוא כזה: נניח ש-\( w \) היא הדוגמה הנגדית המינימלית. נסמן ב-\( i \) את האינדקס של הכניסה הראשונה ב-\( M\left(w\right) \) שאינה אפס וב-\( j \) את האינדקס של הכניסה האחרונה ב-\( M\left(w\right) \) שאינה אפס (למשל, אם \( M\left(w\right)=\left(0,0,1,2,1,0\right) \) אז \( i=3 \) ו-\( j=5 \)). כעת הטענה היא ש-\( M\left(w\right) \) הוא בדיוק מהצורה הבאה: בכניסות \( 1,2,\dots,j-1 \) הוא זהה לגמרי ל-\( G\left(c_{i-1}-1\right) \); בכניסה ה-\( j \)-ית הוא גדול מהכניסה ה-\( j \)-ית של \( G\left(c_{i-1}-1\right) \) ב-1; ובשאר הכניסות הוא 0.

שימו לב שכשאנחנו באים להשתמש במשפט הזה, אנחנו לא יודעים מהו \( w \) ולא מהו \( M\left(w\right) \) ולכן לא יודעים מהם \( i,j \); אבל אנחנו יכולים לעבור סדרתית על כולם. לכל \( i,j \) נתונים אנחנו יכולים לשחק במשחק ה”נניח ש-\( i,j \) הללו הם הערכים הנכונים, נחשב את \( M\left(w\right) \) ונראה אם הוא שווה ל-\( G\left(w\right) \)”.

זה מבלבל, אז בואו נראה דוגמה. יש לנו את המערכת הבריטית, עם המטבעות \( 1,3,6,12,24,30,60,240 \), כלומר \( C=\left(240,60,30,24,12,6,3,1\right) \). אנחנו יודעים ש-\( w=48 \) הוא דוגמה נגדית, ואגלה לכם שזו אכן הדוגמה הנגדית המינימלית. עכשיו, \( M\left(w\right)=\left(0,0,0,2,0,0,0,0\right) \) ולכן \( i=j=4 \). כעת, מהו \( c_{i-1}-1 \)? המטבע \( c_{i-1}=c_{3} \) הוא המטבע 30 (זכרו שאנחנו הולכים מהגדול לקטן), ולכן \( c_{i-1}-1=29 \). מהו \( G\left(29\right) \)? הפעלה של האלגוריתם החמדני נותנת לנו \( G\left(29\right)=\left(0,0,0,1,0,0,1,2\right) \). כעת, הכניסות \( 1,\dots,j-1 \) של \( G\left(29\right) \) הן \( \left(0,0,0\right) \) והכניסה ה-\( j \) כשמוסיפים לה 1 היא 2, ואם משם והלאה יש לנו אפסים קיבלנו על פי המשפט ש-\( M\left(w\right)=\left(0,0,0,2,0,0,0,0\right) \), וזה אכן המצב בפועל. קסם!

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

נתחיל עם עוד הגדרה מתבקשת: נאמר שוקטור \( U \) הוא חמדני אם \( U=G\left(C\cdot U\right) \) (ובמילים - אם הפעלת האלגוריתם החמדני על המספר ש-\( U \) מייצג מחזירה את \( U \)) ונאמר ש-\( U \) מינימלי אם \( U=M\left(C\cdot U\right) \) (במילים - אם הייצוג הטוב ביותר למספר ש-\( U \) מייצג זה הוא עצמו). הטענה שלי היא שוקטורים חמדניים ומינימליים נשארים כאלו גם אם מחסרים להם משהו מהכניסות. בואו נכתוב את זה קצת יותר פורמלית: נשתמש בסימון \( U\subseteq V \) במקרה שבו קיים וקטור \( D \) כך ש-\( U+D=V \) (במתמטיקה יש ל-\( \subseteq \) לרוב שימוש שונה אבל לא נזדקק לשימוש השונה הזה כאן). למשל, אם \( U=\left(1,2,3\right) \) ו-\( D=\left(4,0,3\right) \) אז נקבל \( U+D=\left(5,2,6\right) \).

שימו לב שהגדרנו על וקטורים פעולות “חיבור” ו”כפל” וגם יחס סדר \( \le \) שהן שונות למדי מהפעולות והיחסים שאנחנו מכירים על מספרים; היופי בעניין הוא שהתכונות שאנחנו רגילים להן ממספרים משתמרות ברובן גם עבור הפעולות החדשות. למשל, \( \left(A+B\right)\cdot C=A\cdot C+B\cdot C \). ולמשל \( A\le B \) אם ורק אם \( A+D\le B+D \) (בדקו זאת!). זה מאפשר לנו לתת הוכחה אלגנטית לטענה שלנו. בואו נניח אם כן ש-\( U\le V \) וש-\( V \) חמדני, ונוכיח ש-\( G \) חמדני. לשם כך ניקח \( U^{\prime} \) כלשהו שמייצג את אותו מספר כמו \( U \), דהיינו \( C\cdot U=C\cdot U^{\prime} \), ונראה ש-\( U^{\prime}\le U \) (כלומר, \( U \) הוא הגדול ביותר מבין כל הייצוגים למספר שהוא מייצג, ולכן מה שהאלגוריתם החמדני יחזיר).

כל מה שנצטרך הוא מניפולציות אלגבריות. אם \( U^{\prime}\cdot C=U\cdot C \) אז נקבל ש:

\( \left(V-U+U^{\prime}\right)\cdot C=V\cdot C-U\cdot C+U^{\prime}\cdot C=V\cdot C \)

מה שאומר שהוקטור \( V \) מייצג את אותו המספר כמו \( V-U+U^{\prime} \). מכיוון ש-\( V \) חמדני הוא גדול מכל וקטור אחר שמייצג את אותו מספר, ומכיוון ש-\( V-U+U^{\prime} \) הוא וקטור שכל הכניסות בו חיוביות הוא אכן מייצג מספר. והן כולן חיוביות כי \( U\subseteq V \) - זה המקום שבו אנחנו משתמשים בנתון הזה. ולכן:

\( V-U+U^{\prime}\le V \)

וכעת ניתן לבצע “העברת אגפים” ממש כמו באי-שוויונות במספרים רגילים, ולקבל \( U^{\prime}\le U \), כמבוקש.

הוכחה דומה עובדת גם עבור הטענה שאם \( V \) מינימלי ו-\( U\subseteq V \) אז \( U \) מינימלי. רק צריך לשנות קצת את המשמעות של \( \le \) כך שאם \( \left|A\right|\ge\left|B\right| \) אז \( A\le B \) (קצת מבלבל, אבל זכרו את הרעיון - וקטור מינימלי הוא וקטור בעל משקל מינימלי שהוא הגדול ביותר לקסיקוגרפית; כלומר, הסינון הראשוני הוא על פי המשקל, ומשקל קטן יותר הוא טוב יותר). צריך להוכיח שהמשמעות החדשה עדיין מקיימת את התכונות האלגבריות הנחמדות, אבל אין כאן משהו קשה.

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

עוד תכונה שאשתמש בה בהמשך היא שהפונקציה \( G \) שלוקחת מספר ומתאימה לו את הפתרון החמדני שלו היא משמרת סדר במובן הבא: אם \( x<y \) אז \( G\left(x\right)<G\left(y\right) \). כדי לראות את זה, שימו לב לכך ש-\( U=G\left(x\right)+\left(0,0,\dots,y-x\right) \) הוא ייצוג כלשהו עבור \( y \) ולכן \( U\le G\left(y\right) \). כמו כן בבירור \( G\left(x\right)<U \), כי לקחנו את \( G\left(x\right) \) והוספנו לו עוד משהו. משני אלו קיבלנו ש-\( G\left(x\right)<G\left(y\right) \) - המעבר האחרון הוא שימוש בתכונת הטרנזיטיביות של יחס הסדר \( \le \) ואם זה נראה לכם חשוד, נסו להוכיח שזה עובד.

עכשיו בואו נתחיל את ההוכחה המרכזית שלנו. נניח ש-\( C \) היא מערכת מטבעות לא קנונית, ויהא \( w \) הדוגמה הנגדית הקטנה ביותר לכך. כלומר, \( G\left(w\right)\ne M\left(w\right) \) אבל לכל \( x<w \) מתקיים \( G\left(x\right)=M\left(x\right) \) (הגישה הזו של “בואו ניקח את המינימלי” היא מאוד נפוצה במתמטיקה - היא אוטומטית נותנת לנו כלי נשק חדש ומועיל במהלך ההוכחה שסתם לקחת דוגמה נגדית כלשהי לא היה נותן לנו). בואו נתחיל להבין את התכונות של \( w \) הזה. ראשית כל, אני טוען שאין ל-\( G\left(w\right),M\left(w\right) \) כניסות משותפות ששונות מאפס. בואו נזכר ב-\( w=48 \) של הבריטים: שם \( M\left(w\right)=\left(0,0,0,2,0,0,0,0\right) \) ואילו \( G\left(w\right)=\left(0,0,1,0,1,1,0,0\right) \). ב-\( M\left(w\right) \) הכניסה היחידה שאינה 0 היא הרביעית, ואילו ב-\( G\left(w\right) \) הכניסות שאינן אפס הן 3,5,6. כלומר, אין כניסה ששונה מאפס אצל שניהם, ואני טוען שזה לא מקרי. למה? ובכן, נניח שהכניסה ה-\( k \)-ית בשניהם לא הייתה 0. אז הייתי יכול לחסר ממנה 1 ולקבל מ-\( M\left(w\right) \) ומ-\( G\left(w\right) \) שני וקטורים חדשים שעדיין מייצגים את אותו מספר (המספר \( w-c_{k} \) אם אנחנו רוצים להיות מדוייקים), ועל פי הטענה שהוכחתי לפני רגע על \( U\le V \), הוקטור שנקבל מ-\( M\left(w\right) \) על ידי החיסור יהיה הפתרון המינימלי עבור המספר הזה והוקטור שנקבל מ-\( G\left(w\right) \) יהיה הפתרון החמדני עבור המספר הזה. עכשיו, בגלל ש-\( w \) הוא הדוגמה הנגדית המינימלית לסיטואציה שבה הוקטור החמדני והמינימלי שונים, ינבע ששני הוקטורים שקיבלתי הם זהים, אבל אם כך גם הוקטורים המקוריים שהתחלתי מהם היו צריכים להיות זהים כי כל מה ששיניתי היה לחסר משניהם 1 באותו מקום.

עכשיו בואו נסמן \( M\left(w\right)=\left(m_{1},m_{2},\dots,m_{n}\right) \) וכפי שהבטחתי, נסמן ב-\( i \) את אינדקס הכניסה הראשונה שאינה 0 וב-\( j \) את אינדקס הכניסה האחרונה שאינה 0. אבחנה ראשונה היא ש-\( M\left(w\right)<G\left(w\right) \) על פי הגדרה (כי כל וקטור שמייצג את \( w \) קטן לקסיקוגרפית מ-\( G\left(w\right) \), ואנו מניחים ש-\( M\left(w\right)\ne G\left(w\right) \)). מכיוון ש-\( M\left(w\right),G\left(w\right) \) אינם חולקים כניסות שונות מ-0, הכניסה הראשונה של \( M\left(w\right) \) שאינה אפס חייבת להיות כזו שהיא כן אפס אצל \( G\left(w\right) \); וכדי שעדיין יתקיים \( M\left(w\right)<G\left(w\right) \) נובע שבהכרח יש ל-\( G\left(w\right) \) כניסה מוקדמת יותר ששונה מאפס (למה?) ולכן \( 1<i \). זו לא הסקה טריוויאלית - שוב, אני ממליץ לכם לוודא שאתם מבינים מה הלך פה.

המטרה שלי היא להראות ש-\( M\left(w\right) \) דומה למדי ל-\( G\left(c_{i-1}\right) \), אז בואו ננסה להבין קצת את \( c_{i-1} \) הזה.

מכיוון ש-\( i>1 \) אפשר לדבר על \( c_{i-1} \) (אם \( i=1 \) ואני כותב \( c_{i-1} \) אז כתבתי משהו חסר משמעות כי ה-\( c \)-ים מתחילים מ-1). עכשיו, \( G\left(w\right) \) כולל 1 בכניסה מוקדמת יותר מ-\( i \), כלומר \( w \) מורכב לפחות ממטבע אחד שגדול או שווה ל-\( c_{i-1} \) ומכאן ש-\( w\ge c_{i-1} \). מצאנו חסם מלעיל (מלמעלה) על \( c_{i-1} \). עכשיו בואו נמצא חסם מלרע (מלמטה) עליו: אנחנו יודעים שאם ניקח את \( M\left(w\right) \) אז הכניסה ה-\( j \) תהיה גדולה מאפס. לכן ניתן לחסר ממנה 1, והוקטור שיתקבל יהיה ייצוג של \( w-c_{j} \) (למה?). הוקטור הזה הוא ייצוג מינימלי של \( w-c_{j} \) ומכיוון ש-\( w-c_{j} \) קטן מ-\( w \) ו-\( w \) הוא הערך המינימלי שהייצוג המינימלי שלו אינו חמדני, קיבלנו שהוקטור שלנו (שהוא \( M\left(w\right) \) שבו הכניסה ה-\( j \) הוקטנה ב-1) הוא הייצוג החמדני של \( w-c_{j} \). עכשיו, הייצוג הזה כולל רק את המטבעות שמשתתפים ב-\( M\left(w\right) \), כלומר המטבע בעל הערך הגדול ביותר שמשתתף בו הוא \( c_{i} \). מסקנה: \( w-c_{j}<c_{i-1} \). קחו שניה ותסבירו לעצמכם למה זה נכון, כי עשיתי פה קפיצה קטנה.

ההסבר: אם \( w-c_{j}\ge c_{i-1} \) אז על פי הגדרתו, האלגוריתם החמדני ייקח לפחות את אחת המטבעות \( c_{1},\dots,c_{i-1} \). אנחנו יודעים שהוא לא עשה את זה (אמרתי את זה לפני רגע), ולכן.

אם כן, קיבלנו חסם מלרע עבור \( c_{i-1} \). אם נרכז את מה שכבר מצאנו:

\( w-c_{j}<c_{i-1}\le w \)

זה מראה לנו ש-\( c_{i-1} \) קרוב מאוד ל-\( w \). כמה קרוב? הוא נמצא בטווח קטן יחסית שגודלו \( c_{j} \) וקצהו האחד ב-\( w \) עצמו. בואו נשתמש בזה עכשיו.

נסמן \( V=\left(v_{1},v_{2},\dots,v_{n}\right)=G\left(c_{i-1}-1\right) \). מה שבעצם נותר לנו להוכיח הוא ש-\( v_{k}=m_{k} \) לכל \( 1\le k<j \) וש-\( v_{j}=m_{j}-1 \). הדרך שבה נעשה את זה תהיה לחסום את \( V \) בין שני וקטורים: נראה שהוא קטן מ-\( M\left(w\right) \) אבל שהוא גדול מוקטור אחר שנראה כמעט כמו \( M\left(w\right) \), מה שלא יאפשר ל-\( V \) להיות שונה במיוחד מ-\( M\left(w\right) \) בכל הכניסות עד ה-\( j \)-ית.

נתחיל בלהראות ש-\( V<M\left(w\right) \). מן הסתם \( c_{i-1}-1 \) קטן מ-\( c_{i-1} \) ולכן המטבע \( c_{i-1} \) והגדולות ממנה לא יכולות להיות חלק מהפתרון החמדני עבור \( c_{i-1} \). אבל המטבע \( c_{i} \) בוודאי יהיה, כי הוא המטבע הגדול ביותר שעדיין קטן או שווה ל-\( c_{i-1}-1 \). מכאן ש-\( v_{i}\ne0 \). לכן אפשר להשתמש בתעלול שכבר הפך לשגור אצלנו - להפחית 1 מהכניסה ה-\( i \) הן ב-\( V \) והן ב-\( M\left(w\right) \) ולקבל את \( G\left(c_{i-1}-1-c_{i}\right) \) ואת \( M\left(w-c_{i}\right)=G\left(w-c_{i}\right) \), בהתאמה. כעת, אי השוויון שיש לנו על \( c_{i-1} \) מראה ש-\( c_{i-1}-1-c_{i}<w-c_{i} \), ולכן \( G\left(c_{i-1}-1-c_{i}\right)<G\left(w-c_{i}\right) \), כשהמעבר האחרון נובע מתכונת “שימור הסדר” של פתרונות חמדניים שראינו קודם.

קיבלנו שוקטור א’ יותר קטן מוקטור ב’. אם נחבר לשניהם 1 בכניסה ה-\( i \)-ית זה לא ישנה את הסדר היחסי בין הוקטורים שנקבל, שהם בדיוק \( V,M\left(w\right) \) בהתאמה, ולכן קיבלנו ש-\( V<M\left(w\right) \).

עכשיו בואו נחסום את \( V \) מלרע. לשם כך, בואו ניקח את \( M\left(w\right) \) ונקטין את \( m_{j} \) (הכניסה האחרונה שאינה 0) ב-1. נקבל את הוקטור \( G\left(w-c_{j}\right) \), ומכיוון שכבר ראינו ש-\( w-c_{j}<c_{i-1} \), כלומר ש-\( w-c_{j}\le c_{i-1}-1 \), נקבל ש-\( G\left(w-c_{j}\right)\le G\left(c_{i-1}-1\right)=V \).

מכאן שהצלחנו לחסום את \( V \) כך: \( G\left(w-c_{j}\right)\le V<M\left(w\right) \). זה מעניין, כי \( G\left(w-c_{j}\right) \) ו-\( M\left(w\right) \) הם כמעט אותו וקטור - הם נבדלים רק בכניסה \( m_{j} \) שב-\( M\left(w\right) \) גדולה ב-1. מכאן שעד לכניסה הזו גם \( V \) חייב להיות שווה אליהם (אחרת הוא היה גדול משניהם או קטן משניהם). כעת, מה קורה בכניסה \( m_{j} \)? אנחנו יודעים שקורה אחד משניים: \( v_{j}=m_{j} \) או \( v_{j}=m_{j}-1 \) (אחרת, שוב, \( V \) היה גדול או קטן משני הוקטורים). האם יכול להיות ש-\( v_{j}=m_{j} \)? ובכן, לא: זאת מכיוון שכל הכניסות של \( M\left(w\right) \) שאחרי ה-\( j \)-ית הן אפסים. לכן, אם \( v_{j}=m_{j} \) זה אומר ש-\( V \) זהה ל-\( M\left(w\right) \) ב-\( j \) הכניסות הראשונות וביתר הכניסות הוא שווה או גדול ממנו, ומכאן נובע ש-\( M\left(w\right)\le V \) בסתירה לכך שכבר ראינו ש-\( V<M\left(w\right) \). מכאן ש-\( v_{j}=m_{j}-1 \). ומה על יתר הכניסות של \( V \)? ובכן, הן פשוט לא מעניינות אותנו; השגנו בדיוק את מה שרצינו להשיג. זה מסיים את המשפט ומסיים את כל הטיפול בבעיית “נתונה מערכת מטבעות - האם היא קנונית?”

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

נעבור עכשיו לדבר על הבעיה השניה - בהינתן \( C,x \) לקבוע האם \( G_{C}\left(x\right)=M_{C}\left(x\right) \). מכיוון שלחשב את \( G_{C}\left(x\right) \) זה קל, ברור שה”קושי” של הבעיה מסתמך על כך שבאופן כללי חישוב של \( M_{C}\left(x\right) \) הוא קשה. מה זה אומר, “קשה”? איך מודדים את זה? נתחיל מהשקר שקל יחסית לעכל ונעבור לאמת המסובכת והעגומה יותר. השקר הוא זה: אין לנו דרך “חכמה” לחשב את \( M_{C}\left(x\right) \) ולכן אנחנו פשוט עוברים על כל האפשרויות לייצג את \( x \) בעזרת \( C \) ובודקים מי מהן הכי חסכונית במטבעות. הבעיה היא שיש מספר גדול של אפשרויות: נניח שיש לנו \( n \) סוגי מטבעות ואנחנו תוהים אם אפשר לייצג משהו שגודלו גדול מסכום כל המטבעות. אז יש לנו \( 2^{n} \) אפשרויות לחלוקה שכוללת כל מטבע רק פעם אחת או אפס פעמים, ובפועל יש הרבה יותר חלוקות מזה - מספר החלוקות הוא אקספוננציאלי. לעבור על כולן לוקח המון זמן. זה לא יעיל באופן שבו מודדים “יעילות” במדעי המחשב.

זה סוף השקר, וזה שקר יחסית משביע רצון שמעביר את האינטואיציה. אבל מהי האמת?

האמת היא שאנחנו לא יודעים אם זו בעיה קשה או לא. זה נכון שלחשב את \( M\left(x\right) \) על ידי האלגוריתם “עבור על כל האפשרויות ובדוק” זה לא יעיל, אבל מי אומר לנו שאין אלגוריתם יותר מתוחכם? אנחנו לא מכירים כזה בהכרח, אבל מי אומר שאין? למעשה, בפועל יש אלגוריתמים יותר מתוחכמים, שאני לא מכניס לפוסט הזה כי גם ככה הוא עמוס, אבל גם הם סובלים מאי-יעילות (דהיינו, הם טובים הרבה יותר מהאלגוריתם הנאיבי שהצגתי, אבל זמן הריצה שלהם עדיין איטי למדי). כדי להגיד שהבעיה קשה, אני צריך להוכיח איכשהו טענה כללית: שכל האלגוריתמים שפותרים את הבעיה הם לא יעילים. איך אפשר להקיף את כל האלגוריתמים? זה בוודאי לא משהו טריוויאלי. ולמען האמת, זה אפילו לא נגמר כאן. הבעיה שאני הצגתי היא הבעיה הבאה: בהינתן \( C,x \) האם \( G_{C}\left(x\right)=M_{C}\left(x\right) \)? זו בעיה שהתשובה לה היא “כן/לא”. ייתכן, תיאורטית, שאפשר לענות עליה בלי שנצטרך בכלל לחשב את \( M_{C}\left(x\right) \), כלומר זו עשויה להיות בעיה קלה יותר מאשר חישוב של \( M_{C}\left(x\right) \), ולכן כל הטיעון האינטואיטיבי שנתתי למעלה היה רמאות מובהקת - הוא הסביר למה בעיה אחרת היא קשה. אמנם, אין לי מושג איך לפתור את הבעיה שלי מבלי לפתור את הבעיה האחרת, אבל זה שאני לא חושב על משהו לא אומר שאין.

ברוכים הבאים לעולם של מדעי המחשב התיאורטיים ולתחושה על קצה המזלג של “למה להוכיח חסמים תחתונים זה קשה”. ועדיין, במובן מסויים שהוא פורמלי לגמרי במדעי המחשב התיאורטיים הבעיה נחשבת קשה. באיזה מובן? במובן זה שאם אנחנו מוצאים פתרון יעיל עבורה, הדבר יגרור פתרון יעיל עבור אלפי (עשרות אלפי?) בעיות אחרות במדעי המחשב שלאף אחת מהן לא נמצא עד היום פתרון יעיל שכזה. הבעיות הללו נקראות הבעיות ה-NP-שלמות, ולא אסביר כרגע מהיכן מגיע השם. רק אעיר שמדובר על בעיות שמגיעות משלל תחומים שונים ומנוסחות לעתים בצורות שונות ביותר - ועדיין, באף תחום לא הצליחו לפתור ביעילות אף אחת מהבעיות הללו, מה שמוביל אותנו לאמץ את הנחת העבודה שכנראה אין פתרון יעיל עבורן. אבל הוכחה לכך? אין. הבעיה הזו - כיצד לפתור בעיה NP-שלמה ביעילות או להוכיח שאין פתרון יעיל לאף אחת מהן - נקראת בעיית P=NP והיא הבעיה התיאורטית הפתוחה המרכזית במדעי המחשב.

הערה קטנה למתקדמים, שמי שלא בקיא בתחום יכול לוותר עליה: שימו לב שבניסוח שנתתי, הבעיה אינה ב-NP אלא ב-coNP, מכיוון שלא קיים “עד” ברור לכך ש-\( G_{C}\left(x\right)=M_{C}\left(x\right) \) אבל כן קיים “עד” ברור לכך שהם שונים (בהינתן הפתרון האופטימלי קל לבדוק שהוא שונה מהחמדני). כשאני אומר “הבעיה” אני מתכוון בעצם למשלימה של הבעיה שלנו, וכך גם אפעל בהמשך; הדקות הזו לא קריטית למי שלא מצוי בנבכי ההגדרות הפורמליות.

איך מראים שבעיה היא NP-שלמה? הדרך המקובלת היא באמצעות מעין רקורסיה: לוקחים בעיה שכבר יודעים שהיא NP-שלמה, ומוכיחים שאם אנחנו יודעים לפתור ביעילות את הבעיה החדשה, אז אנחנו יודעים לפתור ביעילות את הבעיה ה-NP-שלמה הישנה (לדבר כזה קוראים רדוקציה). כמובן, רקורסיה צריכה להתחיל מהיכן שהוא, ונקודת ההתחלה הסטנדרטית - השפה ה-NP-שלמה ה”ראשונה”, היא בדרך כלל שפה שנקראת SAT שלא אתאר במפורש כאן.

אז כדי להוכיח שבעיית המטבעות היא NP-שלמה אני צריך לקחת בעיה NP-שלמה קיימת ולעשות רדוקציה שלה אל בעיית המטבעות. מה שאומר שאני קצת מרמה: אני יכול לבחור איזו בעיה NP-שלמה שנוח לי לעבוד איתה בתור “נקודת התחלה”, ומן הסתם בפוסט הזה לא אוכיח שגם היא NP-שלמה. בפועל יש כמה בעיות “סטנדרטיות” שכולם מכירים ונהוג להשתמש בהן או בוריאציות עליהן, ואני הולך להשתמש בוריאציה על בעיה שנקראת Subset Sum. הבעיה המקורית היא כזו: נתונה קבוצה \( S=\left\{ x_{1},x_{2},\dots,x_{n}\right\} \) של מספרים ועוד מספר אחד \( c \). השאלה היא אם קיימת תת-קבוצה של \( S \), שאסמן \( S^{\prime} \), שסכום האיברים בה שווה בדיוק ל-\( c \), כלומר \( \sum_{x\in S^{\prime}}x=c \).

את הבעיה הזו אפשר לנסח בצורה שונה אבל שקולה לגמרי: נתון הוקטור \( X=\left(x_{1},\dots,x_{n}\right) \) של מספרים (אפשר לדרוש במפורש שמספר לא מופיע פעמיים בוקטור אבל זה לא חשוב). האם קיים וקטור בינארי \( A=\left(a_{1},\dots,a_{n}\right) \) כך ש-\( X\cdot A=c \)? כאן “וקטור בינארי” אומר שכל כניסה בוקטור היא 0 או 1.

הוריאציה שאני אשתמש בה מרשה ל-\( A \) להכיל מספרים טבעיים כלשהם, לא רק 0 ו-1 (אבל לא מספרים שליליים). לא אוכיח כאן שהיא NP-שלמה אבל זה תרגיל טוב. בניסוח הזה, הבעיה נראית כמעט לגמרי כמו בעיית המטבעות, בהבדל אחד - אנחנו לא מדברים על אופטימיזציה אלא על היתכנות. חשבו על \( X \) בתור מערכת המטבעות שלנו, אבל ללא דרישה ש-1 יהיה שייך אליה, ואז השאלה היא אם אפשר בכלל לייצג ערך \( c \) נתון במערכת הזו.

אם כן, אני מקבל \( X=\left(x_{1},\dots,x_{n}\right) \) ו-\( c \) ורוצה לייצר שני דברים: מערכת מטבעות \( C \), וערך \( y \) כלשהו, כך שמתקיים ש-\( G_{C}\left(y\right)\ne M_{C}\left(y\right) \) אם ורק אם קיים \( A \) כך ש-\( X\cdot A=c \). זו המהות של רדוקציה - המרה של מקרה לבדיקה של בעיה אחת למקרה לבדיקה של בעיה אחרת.

לכאורה יש לי מגבלה די מהותית - ה”נשק” היחיד שיש לי הוא הפער שיכול להיות קיים בין הפתרון החמדני והאופטימלי. איכשהו אני צריך לנצל אותו כדי לדעת אם בכלל אפשר לייצג ערך כלשהו בעזרת \( X \). אבל אם חושבים קצת על האופן שבו אפשר ליצור מערכות של מטבעות שבהן הפתרון החמדני והאופטימלי לאו דווקא מזדהים, זה לא קשה. מה קרה במערכת הבריטית? היה לנו ערך - 48 - שמיוצג בקלות על ידי מספר קטן כלשהו - 24. אלא שיש מעל 24 מספר גדול יותר, 30, ש”מכריח” את הפתרון החמדני לפספס את 24 ולעבור להתעסק עם מספרים קטנים יותר. על זה אני אבנה את הפתרון שלי, וכדי שיהיה קל להבין אותו אני אסביר מה אני עושה במקרה פרטי.

המקרה הפרטי יהיה \( X=\left(10,20,30,40\right) \) ונראה מה אני עושה עבור \( c \)-ים שונים. יש ב-\( X \) ארבעה איברים, ולכן אני רוצה לבנות מערכת מטבעות \( C \) וערך \( y \) כך שאם \( c \) ניתן לייצוג בידי \( X \), אפשר יהיה לייצג את \( y \) ב-\( C \) באותה הצורה, עם לכל היותר ארבעה איברים; אבל אם אי אפשר, אז כדי לייצג את \( y \) אני אצטרך לפחות חמישה איברים. למעשה, די קל לעשות את זה - נגדיר את \( C \) להיות \( X \) ועוד שני איברים: \( 1 \) (שחייב תמיד להיות ב-\( C \)) ו-\( c-4 \).

בואו נראה איך זה עובד. קודם כל, ניקח \( c=60 \) שאנחנו יודעים שאפשר לייצג ב-\( X \). אז \( C=\left(56,40,30,20,10,1\right) \) ו-\( y=60 \). הפתרון המינימלי במקרה זה הוא \( 60=40+20 \). הפתרון החמדני, לעומת זאת, קודם כל ייקח את \( 56 \), יישאר עם 4, ואז יקח את 1 עוד 4 פעמים - כלומר, גודלו 5.

לעומת זאת, אם ניקח \( c=64 \), שלא ניתן לייצוג על ידי \( X \), אז נקבל \( C=\left(60,40,30,20,10,1\right) \) ו-\( y=64 \). במקרה זה, בבירור הפתרון האופטימלי הוא \( 64=60+1+1+1+1 \) וזהו גם הפתרון החמדני.

ומה קורה אם \( c \) קטן יותר מחלק מהאיברים ב-\( X \), למשל \( c=24 \)? ובכן, בדוגמה הזו אין שום שינוי מהותי - הפתרון החמדני עדיין ייקח את \( c-4 \) בתור האיבר הראשון. מתי כן עשויה להתעורר בעיה? כאשר \( c-4 \) אינו האיבר הגדול ביותר שעדיין קטן מ-\( y \). למשל, אם ניקח \( y=32 \) אז נקבל \( C=\left(40,30,28,20,10,1\right) \), ואז הפתרון החמדני יהיה \( 30+1+1 \), שהוא גם הפתרון האופטימלי. עוד בעיה שיכולה להתעורר היא במקרה שבו \( c \) ממש קטן - למשל, 2.

במקרה הזה אני אבחר את \( y \) להיות גדול מאוד, עם שתי דרכים שונות להקטין אותו - אחת שתכריח אותנו להשתמש ב-1 מכאן ואילך, ואחת שתאפשר לנו להשתמש ב-\( X \). פורמלית, \( y=c+T \) כאשר \( T \) הוא מספר שגדול מהסכום של כל אברי \( X \), ונוסיף למערכת שלנו את \( y-5 \) ואת \( T \) עצמו. במקרה שלנו \( 40+30+20+10=100 \) אז בואו נבחר \( T=200 \) כי אפשר, ואז עבור \( c=32 \) נקבל \( y=232 \) ואת המערכת \( \left(227,200,40,30,20,10,1\right) \). הפתרון החמדני הוא \( 227+1+1+1+1 \) וקל לראות שהוא אופטימלי.

עוד מקרה קצה אחד שבו צריך לטפל הוא זה שבו \( c-4 \) גדול מאחד מאברי \( X \). פתרון פשוט? לכפול את כל אברי \( X \) ב-10 ואת \( c \) ב-10 ולהמשיך משם. אני אשאיר לכם לטפל בפרטים.

זו הייתה רדוקציה במקרה של \( X \) ספציפית, אבל תחליפו את \( 4 \) ב-\( n \) ותקבלו את הרדוקציה עבור \( X \) כללי - שוב, אני ממליץ לאלו מכם שמעוניינים לשבת ולכתוב אותה פורמלית ולהוכיח שהיא עובדת.

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