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

אנדריי קולמוגורוב

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

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

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