פורטל:מדעי המחשב/הידעת?/5

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

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

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