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

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

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

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

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

פרופסור מריה צ'ודנובסקי, ברוכה הבאה לפודקאסט שלנו.

מריה: תודה רבה.

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

מריה: כן, אני אשמח.

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

אבל דברים כאלה פשוט דברים אבסטרקטיים.

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

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

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

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

אז נהייתי מדענית תורת הגרפים.

יוחאי:  ואני חושב שזו התחלה טובה לפודקאסט, מה זה תורת הגרפים?

מריה:  אני אשמח לספר לכם.

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

אז יש הרבה דברים בעולם שאפשר לתאר אותם כיחסים בין זוגות.

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

אם יש לך קבוצה של ערים, יש זוגות של ערים שיש ביניהם טיסה ישירה, וזוגות של ערים שאין ביניהם טיסה ישירה.

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

זה הכל עניין של האם הזוג הזה הוא בקשר או לא בקשר.

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

בדרך כלל כשאנחנו מייצגים גרף אז לנקודות דרך אגב קוראים קודקודים.

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

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

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

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

אז חשוב לזכור את זה.

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

מריה: מייחד? יחסית למה?

עדי:  אולי פשוט תספרי על האפליקציות של מה אפשר להשתמש בגרפים, איפה משתמשים בהם.

מריה: אוקיי, זה אני יכולה לעשות.

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

ויכול מאוד להיות שהרבה אנשים בקהל מבינים בזה הרבה יותר טוב ממני.

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

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

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

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

מסתבר שהתשובה היא אתה לא רוצה אנשים עם הרבה חברים, אתה רוצה אנשים עם הרבה חברים של חברים.

זה המקום הנכון להתחיל.

אז זו דוגמה אחת.

דוגמה אולי יותר עתיקה זה תכנון מסלולים.

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

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

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

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

איזה עוד דוגמאות יש? כל מיני דוגמאות של סקייג'ול.

עדי: מערכת שעות.

מריה: כן, מערכת שעות, חיפשתי את המילה. אז מערכת שעות עם אילוצים.

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

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

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

הו, עוד אחד, עוד אחד, נזכרתי.

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

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

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

אז זו דוגמה שאם מתרגמים אותה לתורת הגרפים, קוראים לזה צביעה של גרף.

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

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

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

מריה:  נכון, נכון מאוד.

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

איך התיאוריה התפתחה? אם אפשר קצת איזה רקע היסטורי מסוים?

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

יוחאי: הגשרים של סנט פטרסבורג, נכון?

מריה:  אני מכירה את זה כהגשרים של קניגסברג.

יוחאי: אה, קניגסברג, סליחה, בקליניגרד, נכון? היום קליניגרד זה קניגסברג.

מריה: גיאוגרפיה זה בטוח לא התחום שלי.

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

אז השאלה של אוילר הייתה, יש את העיר הזאת, שאת שמה אנחנו לא יודעים.

יוחאי: לא, לא, אז את צודקת, זה קניגסברג, היום זה קליניגרד, הרוסים שינו את זה לקליניגרד, אז השם שלה השתנה.

מריה: השקף הראשון בהרצאות שלי זה התמונה הזאת, אז אני מדמיינת אותה לפני העיניים שלי.

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

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

ואם יש כזה מסלול, אז אומרים שבגרף הזה יש מסלול אוילר, וזו בעצם תורה שלמה של מסלולי אוילר.

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

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

והסתבר שזה דבר פנטסטי הגרפים של פיינמן.

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

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

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

מריה: אני אעשה זאת בשמחה.

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

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

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

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

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

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

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

אז קליקה זה קבוצת קודקודים שכל זוג ביניהם מחובר.

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

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

כן? מספר קליקה קבוע שתיים ומספר צביעה עולה ככל שאתה רוצה.

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

עכשיו מסתבר שזה לא שאלה מצוינת, זו שאלה טובה אבל זו לא שאלה מצוינת.

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

קוראים לזה תת גרפים מושרים.

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

ומסתבר שזה מושג מאוד יפה.

עדי: רק בשביל להבהיר, זה לכל תת גרף או כל גרף, שכל פעם אני מוריד קודקוד אחד מכל הקודקודים?

מריה: כל קבוצה של קודקודים שתוריד - זה עדיין צריך להיות נכון.

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

מריה: בדיוק.

עדי:  זה גרף מושלם.

מריה:  זה גרף מושלם, בדיוק.

עדי:  אוקיי, הבנתי.

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

אז שיניתי את הגרף לגמרי. הוא עדיין מושלם.

עדי: אה!

מריה: זה כמו נס בעיניי.

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

כי מההגדרה אין שום סיבה שזה יקרה.

אז זה דבר אחד נחמד על הגרפים המושלמים האלה.

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

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

מריה: במובנים תיאורטיים, כן.

עדי: נגיע לזה אחרי זה, כן.

מריה: האמת שנגיע לזה עכשיו וגם אחרי זה.

אז כשאני אומרת קשה, אני מתכוונת NP שלם.

יוחאי: אני לא בטוח שכל מי שמאזין, אז אולי כדאי לפרט על הסיבוכיות, נכון? אולי כדאי לפרט על זה? -

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

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

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

עדי: אוקיי.

מריה: זה אולי קל להגיד.

עדי:  יופי.

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

אני בטוח לא ידעתי על זה לפני שהתחלתי ללמוד מתמטיקה.

עדי: לא, אני לא חושב שכל מאזין יודע מה זה NP-complete.

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

ברז' אמר, אם אני נותנת לך גרף והוא לא מכיל אף אחת מהדוגמאות הפשוטות האלה, אז הוא חייב להיות מושלם.

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

עדי:  אז זה היה קונג'קצ'ר כזה שלו?

מריה: אז ב-1961 הוא הגדיר גרפים מושלמים, הוא שיער שתי השערות.

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

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

עכשיו, איכשהו יש שני סוגי השערות.

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

אז איכשהו השערת הגרף המושלם החזקה הייתה השערה מהסוג השני.

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

ואז בשנת 2002, המנחה שלי לדוקטורט, עוד שני קולגות ואני, הוכחנו את ההשערה הזאת.

זה היה מאוד מרגש.

עדי: זה היה במהלך הדוקטורט שלך?

מריה: כן, היה במהלך הדוקטורט שלך.

עדי: הו, נהדר, זה אחלה דוקטורט.

מריה: כן.

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

אז התזה שלי היה משהו אחר.

עדי: אבל יש מאמר.

מריה: יש מאמר, אני לא מתלוננת. דרך אגב, המנחה שלי לגמרי צדק.

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

עדי: אבל לא כללת את זה בכלל בתזה?

מריה: לא, תזה זה משהו אחר.

עדי: אה, אוקיי.

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

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

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

אז גמרת תואר ראשון בטכניון, תואר שני בטכניון.

מריה: נכון.

עדי: ואז הלכת לעשות עוד תואר בפרינסטון, ובינגו.

מריה: כן, אז אחרי שנתיים אנחנו הוכחנו את משפט הגרפים המושלם.

עדי: נהדר!

מריה:  כן, זה היה, אני לא מתלוננת, באמת, זו הייתה תקופה מצוינת בחיים שלי.

עדי:  כן, זה נהדר.

מריה: כן, זה היה מאוד כיף.

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

מריה: באמת הרגשה טובה.

עדי: דרך אגב, במתמטיקה ובפיזיקה זה אחרת.

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

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

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

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

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

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

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

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

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

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

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

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

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

אבל מצד שני, הגודל הכי גדול זה באמת הגודל הכי גדול כי הוא יחיד.

אבל את כל הדברים האלה צריך לעבד בראש לאט.

אוקיי, אז זו דוגמא אחת.

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

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

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

ככה שזה מאוד שונה.

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

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

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

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

אני מבין את זה נכון, כלומר זה ההקשר.

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

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

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

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

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

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

מריה:  אני חושבת שהעניין בזה הוא יותר עניין תיאורטי, הוא יותר עניין האם הבעיה הזאת היא NP שלמה או לא, ואם יש פתרון שרץ בזמן אלף בחזקת 100 או אין בחזקת 1000 אז זאת לא בעיה אין פי שלמה.

אני לא חושבת שאנחנו באמת מצפים לבנות מחשבים שיעשו את הדברים האלה.

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

מריה: זה נכון, זה תמיד מאוד בטוח להגיד. אני מסכימה לגמרי.

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

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

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

עדי:  איך זה? תחזרי?

מריה:  רוחב עצי. Treewidth.

עדי:  אה אה אה, רוחב עצי.

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

 אבל אם מישהו באמת רוצה לחפש את זה בגוגל אז קוראים לזה Treewidth.

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

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

ומסתבר שזו שאלה מעניינת והרבה דברים קורים שם.

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

זה בעצם כל המשחק.

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

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

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

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

יוחאי:  אז למשל זה בעיות שאם אנחנו תוחמים אותן, יכול להיות שהן NP למשל, אבל ברגע שתוחמים אותן זה בעיה פתירה, כלומר, איזה בעיות למשל לדוגמה שברגע שתוחמים אותן?

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

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

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

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

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

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

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

ואני חושבת שזה יבוא.

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

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

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

פיזיקאים, אוהבים להגדיר גרף דואלי.

מריה: מה זה אומר?

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

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

הזכרת מאמר אחד, אם תוכלי להרחיב.

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

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

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

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

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

אז איכשהו קליקה שמה שהיא רואה החוצה זה גם קבוצה של קליקות נחמדות.

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

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

אפילו עם הבן שלי בן 11 זה לא קורה הרבה.

אבל הנה, אנשים מאוקספורד, מדענים מאוקספורד רצו לדעת, ואני עניתי.

זו הייתה אינטראקציה מאוד נעימה.

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

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

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

כל גרף שלא מכיל את זה ולא מכיל את זה, הוא מישורי.

אז איכשהו בשבילי זה בעיה מאוד נחמדה, כי אני יודעת בדיוק מה לחפש.

אתה מביא לי גרף, אני יודעת בדיוק מה לחפש.

עכשיו, בשבילנו, אנחנו הרחבנו את זה, אני אומרת אנחנו, כשהייתי בכיתה ז', אנשים הרחיבו את זה, אבל אני נהנית מהפירות.

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

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

אז התשובה קצרה היא: כן.

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

מריה: אז מבחינת אתגרים, אני תמיד נותנת אותה עצה לא להיבהל ולוותר.

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

כי כשעובדים על בעיות קשות, אז זה קשה.

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

זה מה שאני אומרת לכל מי שמוכן להקשיב.

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

אם זה היה ככה, אז זה לא היה מעניין להיות חוקר.

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

אבל לא צריך למהר לזה, לוקח זמן.

אז זו עצה כללית שאני נותנת.

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

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

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

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

אז כשהייתי, אז קראתי, על מספרים ראשוניים...

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

עדי: מספרים ראשונים זה החולשה של כולנו.

מריה:  נכון, לגמרי.

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

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

מריה:  נכון, לגמרי, לגמרי.

יוחאי: פרופסור מריה צ'ונדנובסקי, באמת תודה רבה שהתארחת אצלנו בפודקאסט.

מריה: בשמחה רבה, תודה שהזמנתם אותי, היה לי ממש כיף.

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

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

ואנחנו נמשיך להיות פה בשבילכם ולהמשיך לעשות מדע. תודה רבה.