תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 78:
הדבר מפסיק להיות נכון.
}}
==אי-דחיסות מחרוזות==
למרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של סדרה, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן.
{{משפט
|שם=קיום מחרוזות אי-דחיסות
|תוכן=
נסמן ב<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>.
}}
==כלל השרשרת לסיבוכיות==
| |||