סיבוכיות קולמוגורוב

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

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

סיבוכיות קולמוגורוב איננה תלויה באופן מהותי בשפת התכנות אליה מתייחסים מכיוון שלכל שתי שפות ניתן לכתוב תוכנית בגודל סופי המהווה מפרש (interpreter) של אחת לשנייה. הדבר נכון במיוחד כשמתעניינים בסיבוכיות קולמוגורוב של סדרה של מחרוזות, לסיבוכיות קולמוגורוב קוראים גם "סיבוכיות אלגוריתמית". היא פותחה על ידי אנדריי קולמוגורוב, מתמטיקאי סובייטי, באמצע שנות הששים של המאה העשרים. במקביל הוצע הרעיון על ידי ריי סולומונוף (Ray Solomonoff) וגרגורי צ'ייטין (Gregory Chaitin).

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

דוגמה[עריכת קוד מקור | עריכה]

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

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

אי-כריעות[עריכת קוד מקור | עריכה]

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

סיבוכיות קולמוגורוב והמושג 'מסובך'[עריכת קוד מקור | עריכה]

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

לקריאה נוספת[עריכת קוד מקור | עריכה]

  • Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997
P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.