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

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

1. לכל אורך סדרה נתון, ישנה סדרה לא דחיסה באורך זה.
2. רוב הסדרות אינן דחיסות בצורה משמעותית.

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

יישום: חסמים תחתונים לסיבוכיות אלגוריתמים

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

שימוש להוכחת חסם תחתון על סיבוכיות מציאת פלינדרום

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

נניח שקיימת מ"ט $M$ המצליחה להכריע האם קלט הוא פלינדרום. נתן לה את הקלט $x0^{n}x^{r}$ כאשר:

1. $x$ היא מחרוזת באורך $n$.
2. $0^{n}$ היא רצף של $n$ אפסים.
3. $x^{r}$ היא המחרוזת $x$ בהיפוך.

היות שמדובר בפלינדרום, $M$ חייבת לזהותו ככזה.

כל תו במחרוזת רשום בתא, ויש גבול בינו לבין התא שמימינו. במהלך ריצת האלגוריתם, חוצה ראש המכונה גבול זה מספר פעמים (החציות האי-זוגיות הן לכוון ימין, והאי זוגיות לכוון שמאל). בכל פעם שנחצה הגבול, $M$ נמצאת במצב מסויים. נסמן ב$C(i)$ את סדרת המצבים של החציות של תא $i$. בפרט נתמקד בסדרות החציות של התווים בחלק האמצעי של המחרוזת (החלק המורכב כולו מאפסים, כלומר $n\leq i\leq 2n$).

נניח שזמן ריצת האלגוריתם הוא $t(n)$. בהכרח, סך כל החציות, ובפרט סך כל החציות בתוך החלק האמצעי, הוא $t(n)$ גם כן. מעקרון שובך היונים נובע שקיים $i$ כלשהו בחלק האמצעי (כלומר $n\leq i\leq 2n$) שעבורו $\left|C(i)\right|\leq {\frac {t(n)}{n}}$. כעת נראה שאפשר לתאר את $x$ לחלוטין ע"י השלשה המורכבת מ:

1. המספר $n$
2. המספר $i$
3. הסדרה $C(i)$

נעשה זאת בעזרת מכונה המקבלת את השלשה הנ"ל, ובנתן מחרוזת כלשהי, מסמלצת את פעולת $M$ באופן הבא.

נניח שנתנת המחרוזת כלשהי. אם אורך המחרוזת אינו $n$, המכונה עוצרת. אם כן, המכונה רושמת את המחרוזת, לאחריה $i$ אפסים ומתחילה לסמלץ את $M$. הסמלוץ מתחיל כמובן כאשר ראש $M$ בתא השמאלי ביותר. בכל פעם שנחצה הגבול $i$ לכוון ימין, המכונה המסמלצת בודקת האם מצב $M$ הוא זה שרשום ב$C(i)$: אם לא, היא דוחה את המחרוזת, ואם כן, היא ממשיכה את הסימולציה בחצייה לכוון שמאל במצב הבא. אם לא נותרו מעברים ימינה, המכונה המסמלצת תקבל.

טענה: המכונה המסמלצת מקבלת את $x$ ואך ורק את $x$.

הוכחה: בהנתן קלט $y$, המכונה המסמלצת בודקת האם מתבצעת בדיוק סדרת הפעולות שהיתה $M$ מבצעת על $y0^{n}x^{r}$. היות ש-$M$ מזהה פלינדרומים, המכונה המסמלצת תקבל אם"ם $y=x$.

תרגיל : מדוע יש צורך להעביר למכונה המזהה גם את $n$? ככלות הכל, אם המכונה מזהה פלינדרום $y0^{n}x^{r}$, האם לא נובע כי $y=x$?
המכונה עלולה לזהות גם מחרוזות מהצורה $y=x0^{n}zz^{r}$, ולכן ללא $n$, לא יהיה זיהוי מוחלט של $x$ דווקא.

טענה: קיים קבוע $c$ שעבורו אפשר לתאר כל מחרוזת $x$ בעזרת $\log _{|\Sigma |}(n)+\log _{|\Sigma |}(i)+c{\frac {t(n)}{n}}$ תווים.

הוכחה: בהנתן השלשה, אפשר לייצר את כל המחרוזות באורך $n$, ולבדוק איזו מחרוזת מהן מקבלת המכונה המסמלצת. כבר ראינו שזו בהכרח המחרוזת $x$ המקורית. נניח שדרושים $c$ תווים לתאר מצב של $M$. אם כך, אפשר לתאר את המחרוזת $x$ בעזרת $\log _{|\Sigma |}(n)+\log _{|\Sigma |}(i)+c\left|C(i)\right|$ תווים.

אם כך קבלנו שמתקיים $K(x)\leq \log _{|\Sigma |}(n)+\log _{|\Sigma |}(i)+c{\frac {t(n)}{n}}$ מצד שני ממשפט: קיום מחרוזות אי-דחיסות שראינו מקודם, בהכרח קיים $x$ שעבורו $K(x)\geq |x|=3n$ משילוב שני האי-שוויונים, נקבל $t(n)=\Omega \left(n^{2}\right)$.

חסם תחתון על סיבוכיות מיון מבוסס השוואות

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

יישום: אורך רצפים בסדרות בינאריות רנדומיות

נניח מחרוזת בינרית $x$ שאורכה הוא $n=|x|$. מה אורכי הרצפים של אפסים ואחדות שאפשר לצפות למצוא במחרוזת? נשתמש במשפט: אי-דחיסות משמעותית של רוב המחרוזות שראינו לעיל, לפיו רוב המחרוזות אינן דחיסות ביותר מ-$p$ קבוע כלשהו, כדי לענות על כך. מספיק שנוכיח שתכונה נובעת מכך שמחרוזת איננה דחיסה ביותר מ-$p$, כדי שהדבר יהיה נכון לרוב המחרוזות. כזכור 99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים.

משפט: אם מחרוזת איננה דחיסה ביותר מ-$p$ קבוע כלשהו, אז כל רצף שלה קצר מ: $2\log(n)$.

הוכחה: נניח בשלילה שיש רצף כזה, ובפרט שהמחרוזת היא מהצורה $x=u0^{2\log(n)}v$. נוכל לתאר את $x$ באופן הבא:

1. תיאור אורך $u$ - כפי שאפשר לראות בתרגיל: סיבוכיות מספרים טבעיים $\log(n)(1+o(1))$ תווים.
2. תיאור $u$ - את זאת אפשר לעשות בעזרת $|u|$ תווים.
3. תיאור $v$ (נשים לב שאנו יודעים היכן $u$ מסתיימת) - את זאת אפשר לעשות בעזרת $|v|$ תווים.
4. תיאור איבר הרצף, כלומר "0" או "1" -את זאת אפשר לעשות בעזרת $O(1)$ תווים.
5. תיאור מ"ט הכותבת את $u$, את הרצף, ולאחריה את $v$ - את זאת אפשר לעשות בעזרת $O(1)$ תווים.

נקבל

$n-p\leq K(x)\leq n-2\log(n)+\log(n)+o(\log(n))$

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

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

משפט: אם מחרוזת איננה דחיסה ביותר מ-$p$ קבוע כלשהו, אז יש לה רצף ארוך יותר מ: ${\frac {1}{2}}\log(n)$.

הוכחה: נניח בשלילה שאין רצף כזה, ופרט שאין לה רצף אפסים כזה, ונחלק את המחרוזת ל: ${\frac {n}{{\frac {1}{2}}\log(n)}}={\frac {2n}{\log(n)}}$ חלקים באורך ${\frac {1}{2}}\log(n)$ כל אחד (נתעלם משאריות - אפשר להפוך את ההוכחה למדוייקת יותר במעט מאמץ). לפי ההנחה, כל מחרוזת כזו איננה מורכבת מרצף אפסים, ולכן יש לה רק ${\sqrt {n}}-1$ אפשרויות. נוכל לתאר את $x$ באופן הבא:

1. תיאור כ"א מ${\sqrt {n}}-1$ האפשרויות של כל אחד מ${\frac {2n}{\log(n)}}$ החלקים - את זאת אפשר לעשות בעזרת $\log \left(({\sqrt {(}}n)-1)^{\frac {2n}{\log(n)}}\right)$ תווים.
2. תיאור מ"ט הבונה את המחרוזת מהתיאורים הנ"ל - את זאת אפשר לעשות בעזרת $O(1)$ תווים.

גם כאן נקבל

$n-p\leq K(x)\leq O(1)+\log \left(({\sqrt {(}}n)-1)^{\frac {2n}{\log(n)}}\right)=n-\Omega \left({\frac {\sqrt {n}}{\log(n)}}\right)$

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

הפרק הקודם: סיבוכיות קולמוגורוב

יישומי אי-דחיסות תרגילים

הפרק הבא: הסתברות אוניברסאלית