תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
שורה 265:
<center><math> n - p \leq K(x) \leq n - 2 \log(n) + \log(n) + o(\log(n))</math></center>
מה שמראה שהסדרה דווקא דחיסה.
}}
מחרוזת רנדומית, לכן, כנראה לא תכיל רצפים ארוכים מדי. מצד שני, היא גם לא תכיל רק רצפים קצרים מאד - גם זו תכונה שמקנה מבנה דחיס למחרוזת.
{משפט|תוכן=
אם מחרוזת איננה דחיסה ביותר מ-<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>\sqrt n - 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{n}{\log(n)}
\right)
</math></center>
}}
| |||