תורת החישוביות/סיבוכיות קולמוגורוב

כיצד מחליטים האם מחרוזת היא אקראית או נתונה לפי חוקיות מסויימת? נתבונן בשתי המחרוזות הבאות:

1. 0101010101010101010101010101010101010101
2. 0011010010001000010111011110101010100101

אינטואיטיבית, המחרוזת הראשונה בעלת חוקיות ברורה ואילו השניה נראית "אקראית" וחסרת חוקיות, אולם כיצד אפשר להגדיר זאת בצורה מדוייקת? נשים לב שאפשר לתאר כיצד לייצר את המחרוזת הראשונה בצורה קצרה: "כתוב את הרצף '01' 20 פעמים", אך את ייצור המחרוזת השנייה כנראה שנצטרך לתאר פחות-או-יותר בעזרת תוכנה: "כתוב את הרצף 0011010010001000010111011110101010100101".

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

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

הגדרות

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

הגדרה: סיבוכיות קולמוגורוב (גרסת מ"ט) סיבוכיות קולומוגורוב $K^{TM}(x)$ של מחרוזת $x$, היא אורך הזוג הקצר ביותר של מ"ט וקלט, כך שתוצר פעולת המכונה על הקלט היא $x$: $K^{TM}(x)=\min _{M,w\;:\;M(w)=x}\left|\langle M\rangle \right|+\left|w\right|$

עם זאת, בפרק זה נשתמש בהגדרה גמישה יותר (ומדוייקת פחות), התופסת יותר את רוח הדברים.

ראשית, נניח שיש לנו שפת תכנות אוניברסאלית $U$ כלשהי, דהיינו שפה שבעזרתה אפשר לכתוב כל שפת תכנות אחרת. (לפי תזת צ'רץ'-טיורינג, כל שפה כזו שקולה בעוצמתה למ"ט.) כדוגמה לשפה כזו, אפשר לחשוב על פייתון, שפת C, או כל שפת תכנות כללית אחרת. בהנתן תוכנית $M$ נכתוב $M_{U}(w)$ כדי לתאר את תוצאת ריצתה של התוכנית $M$ על קלט $w$, כאשר מפרשים אותה כתוכנית בשפה $U$.

הגדרה: סיבוכיות קולמוגורוב (גרסת שפה אוניברסאלית מפורשת) סיבוכיות קולומוגורוב $K_{U}(x)$ של מחרוזת $x$, היא אורך הקידוד המינימלי של תוכנית, שעל קלט ריק עוצרת עם הפלט $x$: $K_{U}(x)=\min _{M\;:\;M_{U}(\epsilon )=x}\left|\langle M\rangle \right|$

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

הדבר מוביל אותנו לאבחנה הבאה:

משפט: לכל שתי שפות אוניברסאליות $U$ ו$U'$, קיים קבוע $c=c(U,U')$ המקיים $\forall _{x}\left|K_{U}(x)-K_{U'}(x)\right|\leq c.$

בעקבות משפט זה, ברור שאפשר להחליט שרירותית על שפה אוניברסאלית $U$ כלשהי, ולהגדיר את סיבוכיות קולמוגורוב בעזרתה. כל הגדרה בעזרת שפה אחרת, תיבדל ממנה לכל היותר בקבוע חיבורי כלשהו. נגדיר לכן את ההגדרה האחרונה, בה נשתמש בחלק זה:

הגדרה: סיבוכיות קולמוגורוב סיבוכיות קולומוגורוב $K(x)$ של מחרוזת $x$, היא סיבוכיות הקולמוגורוב שלה תחת שפה אוניברסאלית $U$ כלשהי (שבה משתמשים באופן עקבי עבור כל המחרוזות): $K(x)=K_{U}(x)=\min _{M\;:\;M_{U}(\epsilon )=x}\left|\langle M\rangle \right|$

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

Flag of Ireland

Flag of Belgium

הגדרה: לכל שתי מחרוזת $x$ ו$y$, הסיבוכיות המותנית $K(y|x)$ של $y$ בהנתן $x$ מוגדרת:   $K(y|x)=\min _{M\;:\;M(x)=y}\left|\langle M\rangle \right|$ כלומר, האורך המינימלי של תוכנית שעבור הקלט $x$ פולטת את $y$.

תרגיל : הוכח את הטענות הבאות: $K(xx)=K(x)+O(1)$ $K(x|x)=O(1)$ $K(x|\epsilon )=K(x)$
{{{פתרון}}}

אי-חישוביות פונקציית הסיבוכיות

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

משפט: הפונקציה $K(\cdot )$ אינה ניתנת לחישוב.

הוכחה: (ההוכחה מעט דומה באופייה להוכחת אי-כריעות בעיית העצירה.)

נניח על דרך השלילה שישנה תוכנית $M_{K}$ המחשבת את $K(\cdot )$.

נגדיר תוכנית $M$ בצורה הבאה. $M$ מקבלת מספר חיובי $n$, ומחזירה את המחרוזת הקצרה ביותר $s$ שעבורה $K(s)\geq n$. נשים לב ש$M$ אכן יכולה לעשות זאת. היא מורכבת מלולאה המונה את המחרוזות בסדר לקסיקורפי (דבר שאפשר לממשו בקלות במ״ט), מקריאות ל־$M_{K}(s)$ (שלפי הנחתנו, תמיד מסתיימות), ומהשוואה ל$n$. נגדיר את $u$ כאורך $\langle M\rangle$ בא"ב $\Sigma$.

כעת נגדיר סדרת תוכנית $P_{i}$ (כאשר $i=0,1,2,,\ldots$) באופן הבא. $P_{n}$ קוראת ל$M$ עם פרמטר $n$ כלשהו, ומחזירה את המחרוזת המוחזרת על ידה. נשים לב שתיאור $P$ דורש $u+\log _{\left|\Sigma \right|}\left(n\right)+c$ סימנים, כאשר $c$ הוא קבוע כלשהו:

1. $u$ סימנים נדרשים לתיאור $M_{K}$
2. $\log _{\left|\Sigma \right|}\left(n\right)$ סימנים נדרשים לתיאור $n$.
3. $c$ (קבוע כלשהו) סימנים לתיאור הקריאה ל$M$.

אבל תיאור $P_{n}$ הוא גם תיאור המחרוזת המוחזרת ממנה, נקרא לה $s_{n}$. לפי הגדרת $M$, ל$s_{n}$ נדרשים לפחות $n$ סמלים. קיבלנו, לכן, שבהכרח מתקיים $u+\log _{\left|\Sigma \right|}(n)+c\geq n$. כפי שאפשר לראות בנקל מסדרי הגדילה של שני האגפים בביטוי הקודם, בהכרח יש $n_{0}$ שעבורו, לכל $n\geq n_{0}$, הדבר מפסיק להיות נכון.

אי-דחיסות מחרוזות

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

טענה: קיים קבוע $c$ שעבורו, לכל מחרוזת $x$,   $K(x)\leq |x|+c$

הוכחה: ברור ניתן לתאר את המחרוזת $x$ ע"י התיאור "להלן המחרוזת המבוקשת" שלאחריה פשוט המחרוזת $x$.

פורמאלית, נניח מ״ט $M$ המדפיסה את הקלט שלה: $M(x)=x$. כעת נוכל לתאר כל מחרוזת $x$ בעזרת $\langle M\rangle$ שלאחריה משורשר $x$.

בנוסף, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן.

משפט: קיום מחרוזות אי-דחיסות נסמן ב$n$ מספר טבעי כלשהו. קיימת מחרוזת $x$ בעלת אורך $|x|=n$ שעבורה $K(x)\geq n$

הוכחה: מספר המחרוזות באורך $n$ הוא $\Sigma ^{n}$. מספר התוכנית השונות באורך פחות מ$|x|$ הוא $\sum _{j=0}^{n-1}\left|\Sigma \right|^{j}={\frac {\left|\Sigma \right|^{n-1}-1}{\left|\Sigma \right|-1}}<\Sigma ^{n}$. לכן, קומבינטורית, אין מספיק תוכנית מתאימות.

יתרה מזאת, רוב המחרוזות אינן דחיסות באופן משמעותי.

משפט: אי-דחיסות משמעותית של רוב המחרוזות נסמן ב$p$ מספר טבעי כלשהו. $\left|\{x\in \Sigma ^{*}|k(x)\geq |x|-p\}\right|<{\frac {|\Sigma |^{|x|}(1-|\Sigma |^{-p})}{|\Sigma |-1}}$.

(הוכחת המשפט נמצאת בתרגיל: רוב המחרוזות אינן דחיסות במיוחד.) נשים לב שמשמעות הביטוי היא ש99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים!

כלל השרשרת לסיבוכיות

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

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

משפט: סימטריות אינפורמציה $K(x,y)=K(x)+K(y|x)+\Theta {\bigg (}\log {\Big (}\max \left\{|x|,|y|\right\}{\Big )}{\bigg )}$

מעט אטימולוגיה ותורת האינפורמציה. כאנלוג למושג האינפורמציה ההדדית בתורת האינפורמציה, אפשר להגדיר את האינפורמציה בין שתי מחרוזות כ: $I(x;y)=K(x)-K(x|y)$ כמו במושג המקורי, גם כאן אין סימטריה (יש הבדל בין $I(x;y)$ לבין $I(y;x)$). עם זאת, המשפט כאן מראה כי ההבדל בין שני הגדלים הוא לכל היותר לוגריתמי באורך המחרוזות, ולכן יש סימטריות מסויימת.

הוכחה: ראשית נראה כי

$K(x,y)\leq K(x)+K(y|x)+\Theta \left(\log(\max(|x|,|y|))\right)$

כדי לייצר תכנית הפולטת את $x,y$, נוכל להשתמש בתכנית הבאה, המורכבת מהחלקים הבאים:

1. הוראה להריץ שתי תכניות (שתיאורן מופיע בהמשך) ולשרשר את התוצאה - לכך יש צורך במספר תווים קבוע.
2. תיאור של אורך התכנית הראשונה - לכך יש צורך ב$O\left(\log(x)\right)$ תווים.
3. תכנית המייצרת את $x$ - לכך יש צורך ב$K(x)$ תווים.
4. תכנית המייצרת את $y$ בהנחה שx ידוע - לכך יש צורך ב$K(y|x)$ תווים.

כעת נראה כי

$K(x,y)\geq K(x)+K(y|x)+\Omega \left(\log(\max(|x|,|y|))\right)$

כדי להוכיח את כוון זה, נגדיר את הקבוצה

$A=\{(u,z):K(u,z)\leq K(x,y)\}$

,

דהיינו, קבוצת זוגות המחרוזות ששרשורן המופרד נתן לתיאור לא ארוך יותר מאשר שרשורן המופרד של $x$ ו$y$. בנוסף, נגדיר את

$A_{x}=\{z:K(x,z)\leq K(x,y)\}\subset A$

כקבוצת זוגות המחרוזות המקיימות זאת כשהמחרוזת הראשונה מבין השתיים היא $x$.

נשים לב שלו היינו יודעים את $K(x,y)$, אפשר היה למנות את איבריהן של $A$ ו$A_{x}$ באופן דומה לזה שעשינו במקומות אחרים בספר. כדי למנות את איברי $A$, נמנה בסדר לקסיקוגרפי את כל ה באורך לכל היותר $\left|\Sigma \right|^{K(x,y)}$. נריץ את המכונה הראשונה צעד אחד, את 2 המכונות הראשונות כ"א 2 צעדים, את 3 המכונות הראשונות כ"א 3 צעדים, וכו'. בכל פעם שמכונה מסיימת ופולטת זוג-מופרד $u,z$, נרשום זוג זה בצד. כדי למנות את $A_{x}$, נתעלם מהפלטים בהם האיבר הראשון בזוג הנפלט אינו $x$. נגדיר את המספר השלם $e$ כך שיתקיים

$|\Sigma |^{e}\leq \left|A_{x}\right|\leq |\Sigma |^{e+1}$

.

היות שיש מניה של איברי $A_{x}$, אזי בהנתן $x$, נוכל להשתמש במניה זו כדי לתאר את $y$: פשוט נתאר את האינדקס של הזוג ש$y$ הוא איברו השני באיברים אלו. את זה, כמובן, נתן לעשות ע"י $\Theta (e)$ תווים. בהנתן אינדקס זה, נריץ את אותה שיטת מנייה, ונשחזר את $y$. קבלנו כי

$K(y|x)\leq e+O(1)$

.

באותו אופן אפשר להראות כי

$K(x,y)\leq \log _{|\Sigma |}(|A|)+O(1).$

נגדיר כעת את הקבוצה $B$ כך:

$B=\{u|\left|A_{u}\right|\geq |\Sigma |^{e}\}.$

אז לפי הבניה,

$\left|B\right|\leq {\frac {\left|A\right|}{|\Sigma |^{e}|}}\leq {\frac {|\Sigma |^{K(x,y)+O(1)}}{|\Sigma |^{e}}}.$

קל לראות כי $x\in B$ ולכן אפשר לתאר מחרוזת זו בעזרת האינדקס שלה בקבוצה זו. נקבל

$K(x)\leq |e|+\log _{|\Sigma |}\left({\frac {|\Sigma |^{K(x,y)+O(1)}}{|\Sigma |^{e}}}\right)+2\log _{|\Sigma |}(e)\leq K(x,y)-e+O\left(\log(\max(|x|,|y|))\right)$

.

הוכחת הכוון השני מסתיימת ע"י הצבת הגדרת $e$.

הפרק הקודם: משפט הרקורסיה

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

הפרק הבא: יישומי אי-דחיסות