ויקיספר

תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Gran (שיחה | תרומות)
2,595 עריכות
←‏הגדרות: כנראה לכך הכוונה
Atavory (שיחה | תרומות)
7,521 עריכות
אין תקציר עריכה
שורה 1:
{{תורת החישוביות}}
 
{{בעבודה}}
 
כיצד מחליטים האם מחרוזת היא אקראית או נתונה לפי חוקיות מסויימת? נתבונן בשתי המחרוזות הבאות:
שורה 9 ⟵ 11:
 
בפרק זה נגדיר במדויק את הרעיון הנ״ל, תוך שימוש ב[[תורת_החישוביות/מכונת_טיורינג_אוניברסלית|מ״ט אוניברסליות]]. רעיון זה מקשר בין תחום החישוביות לתחומים אחרים, כגון {{וק|תורת האינפורמציה}}, ויש לו מספר שימושים. בסעיף [[#הגדרות|הגדרות]] נגדיר את {{וק|סיבוכיות קולמוגורוב|סיבוכיות הקולמוגורוב}} של מחרוזת בינארית כאורך הקצר ביותר של מ"ט המייצרת אותה. בסעיף [[#אי-חישוביות פונקציית הסיבוכיות|אי-חישוביות פונקציית הסיבוכיות]] נראה שפונקציה זו איננה ניתנת לחישוב, וב[[#אי-דחיסות מחרוזות|אי-דחיסות מחרוזות]] נראה שלרוב המחרוזות יש סיבוכיות קולמוגורוב קרובה למדי לאורכן (זו טענה קומבינטורית חזקה למדי, לפיה את רוב המחרוזות אי אפשר לדחוס). בסעיפים [[#יישום: חסמים תחתונים לסיבוכיות אלגוריתמים|יישום: חסמים תחתונים לסיבוכיות אלגוריתמים]] ו[[#יישום: אורך רצפים בסדרות בינאריות רנדומיות|יישום: אורך רצפים בסדרות בינאריות רנדומיות]], נראה כיצד לנצל טענה קומבינטורית חזקה זו. לבסוף, ב[[#כלל השרשרת לסיבוכיות|כלל השרשרת לסיבוכיות]], נדון קצת יותר בסיבוכיות תיאור מחרוזת בהנחה שאחרת כבר תוארה.
 
==הגדרות==
 
שורה 74 ⟵ 77:
<math>n \geq n_0</math>,
הדבר מפסיק להיות נכון.
}}
 
==אי-דחיסות מחרוזות==
 
למרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של סדרה כלשהי, אפשר להשתמש בו כדי להוכיח שלמרבית המחרוזות, סיבוכיות הקולמוגורוב שלהן היא פחות או יותר אורך המחרוזת. בהמשך נראה יישומים שונים לכך (לדוגמה, הוכחת חסמים ל[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה|סיבוכיות אלגוריתמים]]).
 
 
ראשית, נראה שעל אף שאי אפשר לחשב את סיבוכיות הקולמוגורוב של סדרה, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן.
{{משפט
|שם=קיום מחרוזות אי-דחיסות
|תוכן=
נסמן ב<math>n</math> מספר טבעי כלשהו.
קיימת מחרוזת <math>x</math> בעלת אורך <math>n</math> שעבורה
<math>K(x) \geq |x| = n</math>
}}
 
{{הוכחה|1=
מספר המחרוזות באורך
<math>n</math>
הוא
<math>\Sigma^n</math>.
מספר מ"ט השונות באורך פחות מ<math>|x|</math>
הוא
<math>\sum_{j = 0}^{n - 1} \left|\Sigma\right|^j = \frac{\left|\Sigma\right|^{n - 1} - 1}{\left|\Sigma\right| - 1} < \Sigma^n </math>.
לכן, קומבינטורית, אין מספיק מ"ט מתאימות.
 
}}
 
יתרה מזאת, רוב המחרוזות אינן דחיסות באופן משמעותי.
{{משפט
|שם=אי-דחיסות משמעותית של רוב המחרוזות
|תוכן=
נסמן ב<math>p</math> מספר טבעי כלשהו.
 
<center><math>
\left|
\{
x \in \Sigma^* |
k(x) \geq |x| - p
\}
\right|
<
\frac
{
|\Sigma|^{|x|} (1 - |\Sigma|^{-p})
}
{
|\Sigma| - 1
}
</math></center>.
}}
(הוכחת המשפט נמצאת ב[[תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים#רוב המחרוזות אינן דחיסות במיוחד|תרגיל: רוב המחרוזות אינן דחיסות במיוחד]].)
נשים לב שמשמעות הביטוי היא ש99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים!
 
 
נציין שלכוון השני ישנו כמובן החסם הטריוויאלי הבא.
{{טענה|תוכן=
קיים קבוע <math>c</math> שעבורו, לכל מחרוזת <math>x</math>,
<math>K(x) \leq |x| + c</math>
}}
 
{{הוכחה|1=
ברור שאפשר לתאר את המחרוזת <math>x</math> ע"י התיאור "להלן המחרוזת המבוקשת" שלאחריה פשוט המחרוזת <math>x</math>.
 
פורמאלית, נניח מ"ט <math>M</math> הדפיסה את הקלט שלה:
<math>M(x) = x </math>.
נוכל לתאר כל מחרוזת <math>x</math> בעזרת
<math>\langle M \rangle </math> שלאחריה משורשר <math>x</math>.
}}
 
==יישום: חסמים תחתונים לסיבוכיות אלגוריתמים==
 
[[#אי-דחיסות מחרוזות|אי-דחיסות מחרוזות]] משמש לעתים להוכחת חסמים תחתונים על זמני הריצה של [[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה|סיבוכיות]] אלגוריתמים. הרעיון הכללי הוא כזה. בהנתן קלט <math>x</math> כלשהו, מראים שאלגוריתם "יעיל מדי" הפועל עליו, מניב תיאור קצר במיוחד שלו, בסתירה לכך שלכל אורך נתון, יש לפחות מחרוזת אחת בלתי דחיסה לחלוטין.
 
 
===שימוש להוכחת חסם תחתון על סיבוכיות מציאת פלינדרום===
 
בעזרת סיבוכיות קולמוגורוב, אפשר להראות ש[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/סדרי גדילה|סיבוכיות]] הכרעה האם מחרוזת היא [[w:פלינדרום|פלינדרום]] ע"י מ"ט בעלת סרט יחיד היא לפחות ריבועית באורך הקלט.
 
נניח שקיימת מ"ט <math>M</math> המצליחה להכריע האם קלט הוא פלינדרום. נתן לה את הקלט
<math>x0^nx^r</math>
כאשר:
#<math>x</math> היא מחרוזת באורך <math>n</math>.
#<math>0^n</math> היא רצף של <math>n</math> אפסים.
#<math>x^r</math> היא המחרוזת <math>x</math> בהיפוך.
 
[[File:Kolmogorov complexity palindrome prob.png|בעיית זיהוי הפלינדרום]]
 
היות שמדובר בפלינדרום, <math>M</math> חייבת לזהותו ככזה.
 
כל תו במחרוזת רשום בתא, ויש גבול בינו לבין התא שמימינו. במהלך ריצת האלגוריתם, חוצה ראש המכונה גבול זה מספר פעמים (החציות האי-זוגיות הן לכוון ימין, והאי זוגיות לכוון שמאל). בכל פעם שנחצה הגבול, <math>M</math> נמצאת במצב מסויים. נסמן ב<math>C(i)</math> את סדרת המצבים של החציות של תא <math>i</math>. בפרט נתמקד בסדרות החציות של התווים בחלק האמצעי של המחרוזת (החלק המורכב כולו מאפסים, כלומר <math>n \leq i \leq 2n</math>).
 
נניח שזמן ריצת האלגוריתם הוא
<math>t(n)</math>.
בהכרח, סך כל החציות, ובפרט סך כל החציות בתוך החלק האמצעי, הוא <math>t(n)</math> גם כן. מ[[w:עקרון שובך היונים|עקרון שובך היונים]] נובע שקיים <math>i</math> כלשהו בחלק האמצעי (כלומר <math>n \leq i \leq 2n</math>)
שעבורו
<math>\left|C(i)\right| \leq \frac{t(n)}{n}</math>.
כעת נראה שאפשר לתאר את <math>x</math> לחלוטין ע"י השלשה המורכבת מ:
# המספר <math>n</math>
# המספר <math>i</math>
# הסדרה <math>C(i)</math>
 
נעשה זאת בעזרת מכונה המקבלת את השלשה הנ"ל, ובנתן מחרוזת כלשהי, מסמלצת את פעולת <math>M</math> באופן הבא.
 
[[File:Kolmogorov complexity palindrome prob crossings.png|מעברי האלגוריתם]]
 
נניח שנתנת המחרוזת כלשהי. אם אורך המחרוזת אינו <math>n</math>, המכונה עוצרת. אם כן, המכונה רושמת את המחרוזת, לאחריה <math>i</math> אפסים ומתחילה לסמלץ את <math>M</math>. הסמלוץ מתחיל כמובן כאשר ראש <math>M</math> בתא השמאלי ביותר. בכל פעם שנחצה הגבול <math>i</math> לכוון ימין, המכונה המסמלצת בודקת האם מצב <math>M</math> הוא זה שרשום ב<math>C(i)</math>: אם לא, היא דוחה את המחרוזת, ואם כן, היא ממשיכה את הסימולציה בחצייה לכוון שמאל במצב הבא. אם לא נותרו מעברים ימינה, המכונה המסמלצת תקבל.
 
{{טענה|תוכן=
המכונה המסמלצת מקבלת את <math>x</math> ואך ורק את <math>x</math>.
}}
 
{{הוכחה|1=
בהנתן קלט <math>y</math>, המכונה המסמלצת בודקת האם מתבצעת בדיוק סדרת הפעולות שהיתה <math>M</math> מבצעת על
<math>y0^nx^r</math>.
היות ש-<math>M</math> מזהה פלינדרומים, המכונה המסמלצת תקבל אם"ם
<math>y = x</math>.
}}
 
{{תרגיל|יישור=ימין|
שאלה=מדוע יש צורך להעביר למכונה המזהה גם את <math>n</math>? ככלות הכל, אם המכונה מזהה פלינדרום <math>y0^nx^r</math>, האם לא נובע כי <math>y = x</math>?
|פתרון=
המכונה עלולה לזהות גם מחרוזות מהצורה
<math>y = x0^nzz^r</math>,
ולכן ללא <math>n</math>, לא יהיה זיהוי מוחלט של <math>x</math> דווקא.
}}
 
{{טענה|תוכן=
קיים קבוע <math>c</math> שעבורו אפשר לתאר כל מחרוזת <math>x</math> בעזרת
<math>\log_{|\Sigma|}(n) + \log_{|\Sigma|}(i) + c \frac{t(n)}{n}</math> תווים.
}}
 
{{הוכחה|1=
בהנתן השלשה, אפשר לייצר את כל המחרוזות באורך <math>n</math>, ולבדוק איזו מחרוזת מהן מקבלת המכונה המסמלצת. כבר ראינו שזו בהכרח המחרוזת <math>x</math> המקורית.
נניח שדרושים <math>c</math> תווים לתאר מצב של <math>M</math>. אם כך, אפשר לתאר את המחרוזת <math>x</math> בעזרת
<math>\log_{|\Sigma|}(n) + \log_{|\Sigma|}(i) + c \left| C(i) \right|</math>
תווים.
}}
 
 
אם כך קבלנו שמתקיים
<math>K(x) \leq \log_{|\Sigma|}(n) + \log_{|\Sigma|}(i) + c \frac{t(n)}{n}</math>
מצד שני מ[[#אי-דחיסות מחרוזות|משפט: קיום מחרוזות אי-דחיסות]] שראינו מקודם, בהכרח קיים <math>x</math> שעבורו
<math>K(x) \geq |x| = 3n</math>
משילוב שני האי-שוויונים, נקבל
<math>t(n) = \Omega\left(n^2\right)</math>.
 
===חסם תחתון על סיבוכיות מיון מבוסס השוואות===
 
בעזרת סיבוכיות קולמוגורוב אפשר להראות
[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים/החסם התחתון על מיון מבוסס-השוואות|חסם תחתון על מיון מבוסס השוואות]]. הרעיון הוא שמיון יעיל מדי היה מוצא דרך לדחוס פרמוטציות מעבר למה שאפשרי קומבינטורית.
 
==יישום: אורך רצפים בסדרות בינאריות רנדומיות==
 
נניח מחרוזת בינרית <math>x</math> שאורכה הוא <math>n =|x|</math>. מה אורכי הרצפים של אפסים ואחדות שאפשר לצפות למצוא במחרוזת? נשתמש ב[[#אי-דחיסות מחרוזות|משפט: אי-דחיסות משמעותית של רוב המחרוזות]] שראינו לעיל, לפיו רוב המחרוזות אינן דחיסות ביותר מ-<math>p</math> קבוע כלשהו, כדי לענות על כך. מספיק שנוכיח שתכונה נובעת מכך שמחרוזת איננה דחיסה ביותר מ-<math>p</math>, כדי שהדבר יהיה נכון לרוב המחרוזות. כזכור 99.9% מהמחרוזות אינן דחיסות ביותר מ10 תווים.
 
{{משפט|תוכן=
אם מחרוזת איננה דחיסה ביותר מ-<math>p</math> קבוע כלשהו, אז כל רצף שלה קצר מ:
<math>2 \log(n)</math>.
}}
 
{{הוכחה|1=
נניח בשלילה שיש רצף כזה, ובפרט שהמחרוזת היא מהצורה
<math>x = u0^{2 \log(n)} v</math>.
נוכל לתאר את
<math>x</math>
באופן הבא:
# תיאור אורך <math>u</math> - כפי שאפשר לראות ב[[תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים#סיבוכיות מספרים טבעיים|תרגיל: סיבוכיות מספרים טבעיים]] <math>\log(n) ( 1 + o(1))</math> תווים.
# תיאור <math>u</math> - את זאת אפשר לעשות בעזרת <math>|u|</math> תווים.
# תיאור <math>v</math> (נשים לב שאנו יודעים היכן <math>u</math> מסתיימת) - את זאת אפשר לעשות בעזרת <math>|v|</math> תווים.
# תיאור איבר הרצף, כלומר "0" או "1" -את זאת אפשר לעשות בעזרת <math>O(1)</math> תווים.
# תיאור מ"ט הכותבת את <math>u</math>, את הרצף, ולאחריה את <math>v</math> - את זאת אפשר לעשות בעזרת <math>O(1)</math> תווים.
 
נקבל
<center><math> n - p \leq K(x) \leq n - 2 \log(n) + \log(n) + o(\log(n))</math></center>
שכמובן אינו אפשרי לערכי <math>n</math> גדולים, מה שמראה שהסדרה דווקא דחיסה.
}}
 
מחרוזת רנדומית, לכן, כנראה לא תכיל רצפים ארוכים מדי. מצד שני, היא גם לא תכיל רק רצפים קצרים מאד - גם זו תכונה שמקנה מבנה דחיס למחרוזת.
{{משפט|תוכן=
אם מחרוזת איננה דחיסה ביותר מ-<math>p</math> קבוע כלשהו, אז יש לה רצף ארוך יותר מ:
<math>\frac{1}{2} \log(n)</math>.
}}
 
{{הוכחה|1=
נניח בשלילה שאין רצף כזה, ופרט שאין לה רצף אפסים כזה, ונחלק את המחרוזת ל:
<math>\frac{n}{\frac{1}{2} \log(n)} = \frac{2n}{\log(n)}</math>
חלקים באורך <math>\frac{1}{2} \log(n)</math> כל אחד (נתעלם משאריות - אפשר להפוך את ההוכחה למדוייקת יותר במעט מאמץ).
לפי ההנחה, כל מחרוזת כזו איננה מורכבת מרצף אפסים, ולכן יש לה רק
<math>\sqrt n - 1</math>
אפשרויות.
נוכל לתאר את
<math>x</math>
באופן הבא:
# תיאור כ"א מ<math>\sqrt n - 1</math> האפשרויות של כל אחד מ<math>\frac{2n}{\log(n)}</math> החלקים - את זאת אפשר לעשות בעזרת <math>\log\left(
(\sqrt(n) - 1)^{\frac{2n}{\log(n)}}
\right)
</math> תווים.
# תיאור מ"ט הבונה את המחרוזת מהתיאורים הנ"ל - את זאת אפשר לעשות בעזרת <math>O(1)</math> תווים.
 
גם כאן נקבל
<center><math>
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)
</math></center>
מה ששוב כמובן אינו אפשרי לערכי <math>n</math> גדולים, ושוב מראה שהסדרה דווקא דחיסה.
}}
 
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/סיבוכיות_קולמוגורוב"