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

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

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

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

דוגמה

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

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

אי-כריעות

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

סיבוכיות קולמוגורוב והמושג 'מסובך'

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

ביסוס מתמטי

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

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

נניח שכל תיאור מתאר אובייקט אחד לכל היותר. כלומר, יש שיטת מפרט $D$ שמשייכת לכל היותר אובייקט אחד $x$ לתיאור $y$. זה אומר ש-$D$ היא פונקציה מקבוצת התיאורים, נניח $Y$, לתוך קבוצת האובייקטים, נניח $X$. נראה גם הגיוני לדרוש שלכל אובייקט $x$ ב-$X$ יהיה תיאור $y$ ב-$Y$ כך שניתן לכתוב $D(y)=x$. כדי להפוך תיאורים לשימושיים הם אמורים להיות סופיים. זה אומר שיש רק תיאורים רבים לספור. מכיוון שיש תיאור לכל אובייקט, יש גם רק אובייקטים רבים שניתן לתאר. כיצד מודדים את מורכבות התיאורים?

בהסתמך על תורת החישוביות, מבטאים תיאורים כרצפים סופיים של 0 ו-1. בטכנולוגיית תקשורת, אם שיטת המפרט $D$ ידועה גם לשולח וגם למקבל, אזי ניתן להעביר הודעה $x$ משולח למקבל על ידי שידור הרצף של 0 ו-1 של תיאור $y$ עם $D(y)=x$. העלות של שידור זה נמדדת לפי מספר ההתרחשויות של 0 ו-1 ב-$y$, כלומר באורך של $y$. העלות הנמוכה ביותר של שידור של $x$ נתונה באורך של $y$ הקצר ביותר כך ש-$D(y)=x$. בתקשורת בוחרים את העלות הנמוכה ביותר של שידור כמורכבות התיאורית של $x$ לפי שיטת המפרט $D$.

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

בתיאור הסיבוכיות לא באמת מעוניינים באופטימיות ביחס לכל שיטות התיאור. כדי שמפרטים יהיו שימושיים בכלל, יש צורך שהמיפוי מ-$y$ ל-$D(y)$ יהיה ניתן לביצוע בצורה יעילה. כלומר, זה יכול לפחות באופן עקרוני להתבצע על ידי בני אדם או מכונות. תפיסה זו מעבירה את השאלה לתחום פונקציות ניתנות לחישוב חלקיות. לפי נקודות מבט מתמטיות מקובלות, זה עולה בקנה אחד עם הרעיון האינטואיטיבי של חישוב יעיל. קבוצת הפונקציות הניתנות לחישוב חלקיות מכילה פונקציה אופטימלית אשר ממזערת את אורך התיאור של כל פונקציה אחרת כזו. פונקציה זו תסומן ב-₀$D$. עבור כל פונקציה אחרת לחישוב $D$, עבור כל האובייקטים $X$, יש תיאור של $x$ מתחת ל-₀$D$ שהוא קצר יותר מכל תיאור של $x$ מתחת ל-$D$. (כלומר, קצר יותר עד קבוע מתוסף שאינו תלוי ב-$x$.) לפי חשיבה זו מורכבותו של אובייקט היא תכונה אובייקטיבית של האובייקט המתואר בלבד: היא תכונה מהותית של אותו אובייקט, והיא אינה תלויה בפורמליזם התיאור. ניתן להתייחס למורכבות זו כתוכן מידע מוחלט: כמות המידע שיש להעביר בין כל השולחים והמקבלים כאשר הם מעבירים את המסר בהיעדר כל ידע אפריורי אחר המגביל את תחום ההודעה.

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

לקריאה נוספת

• Ming Li and Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, Springer, 1997 הפרק הראשון של הספר
• Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997

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

הערך באדיבות ויקיפדיה העברית, קרדיט,
רשימת התורמים
רישיון cc-by-sa 3.0

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