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