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

נניח שאנו רוצים לתאר אובייקט נתון על ידי מחרוזת בינארית סופית. אין זה מן העניין אם לאובייקט יש תיאורים רבים; עם זאת, כל תיאור צריך לתאר רק אובייקט אחד. מבין כל התיאורים של אובייקט ניתן לקחת את אורך התיאור הקצר ביותר כמדד לסיבוכיות האובייקט. טבעי לקרוא לאובייקט 'פשוט' אם יש לו לפחות תיאור קצר אחד, ולקרוא לו 'מסובך' אם כל התיאורים שלו ארוכים.
אבל כעת הגדרה זו נופלת למלכודת המתוארת בפרדוקס של ברי, שבו מגדירים מספר טבעי כ"מספר הכי פחות טבעי שלא ניתן לתאר בפחות מ-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) יהיה ניתן לביצוע בצורה יעילה. כלומר, זה יכול לפחות באופן עקרוני להתבצע על ידי בני אדם או מכונות. תפיסה זו מעבירה את השאלה לתחום פונקציות ניתנות לחישוב חלקיות. לפי נקודות מבט מתמטיות מקובלות, זה עולה בקנה אחד עם הרעיון האינטואיטיבי של חישוב יעיל. קבוצת הפונקציות הניתנות לחישוב חלקיות מכילה פונקציה אופטימלית אשר ממזערת את אורך התיאור של כל פונקציה אחרת כזו. פונקציה זו תסומן ב-0 D. עבור כל פונקציה אחרת לחישוב  D, עבור כל האובייקטים  X, יש תיאור של  x מתחת ל-0 D שהוא קצר יותר מכל תיאור של  x מתחת ל- D. (כלומר, קצר יותר עד קבוע מתוסף שאינו תלוי ב- x.) לפי חשיבה זו מורכבותו של אובייקט היא תכונה אובייקטיבית של האובייקט המתואר בלבד: היא תכונה מהותית של אותו אובייקט, והיא אינה תלויה בפורמליזם התיאור. ניתן להתייחס למורכבות זו כתוכן מידע מוחלט: כמות המידע שיש להעביר בין כל השולחים והמקבלים כאשר הם מעבירים את המסר בהיעדר כל ידע אפריורי אחר המגביל את תחום ההודעה.
בגדול, זה אומר שכל תחבירי התיאור שהם חזקים מספיק כדי לבטא את הפונקציות הניתנות לחישוב חלקיות הם תמציתיים בערך באותה מידה. ניתן לבטא את כל האלגוריתמים בכל שפת תכנות כזו באופן תמציתי באותה מידה, עד למונח קבוע מתוסף קבוע. התועלת המדהימה והנכונות המובנית של התיאוריה של מורכבות קולמוגורוב נובעת מעצמאות זו של שיטת התיאור.