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

רוב המחרוזות אינן דחיסות במיוחד

הוכח את משפט: אי-דחיסות משמעותית של רוב המחרוזות

הפתרון

מספר המחרוזות באורך $|x|$ הוא $\left|\Sigma \right|^{|x|}$. מספר מ"ט שתיאורן קצר מאשר $|x|-p$ הוא $\sum _{i=0}^{|x|-p-1}\left|\Sigma \right|^{i}={\frac {\left|\Sigma \right|^{|x|-p}-1}{\left|\Sigma \right|-1}}$. המשפט מתקבל ע"י חיסור שני ביטויים אלה עם מעט פישוטים.

סיבוכיות מספרים טבעיים

$n$ הוא מספר טבעי כלשהו, ו$x$ היא מחרוזת. רוצים לתאר את $n,x$, כלומר לתאר הן את המספר, והן את המחרוזת, כך שברור היכן המספר מסתיים והמחרוזת מתחילה.

הוכח שמתקיים

$K(n,x)\leq 2\log(\log(n))+\log(n)+O(1)+K(x)$

רמז: הכפל כל תו בחקל מתיאור $n$.

הפתרון

נתאר את השרשור באופן הבא:

1. נקח את הייצוג בא"ב של $n$, ונרשום כל תו פעמיים - זה יצריך $2\log(\log(n))+O(1)$ תווים.
2. נשתמש ברצף שני התווים $01$ כדי לסמן שכאן נגמר תיאור אורך המספר - זה מצריך $O(1)$ תווים.
3. נתאר את המספר - זה מצריך $\log(n)$ תווים.
4. נתאר את $x$ - זה מצריך $K(x)$ תווים.
5. נתאר את הסכמה בעזרת $O)1($ תווים.

סיבוכיות שרשרור נתן להפרדה בעזרת רכיבי הסיבוכיות הבסיסיים

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

1. $K(x,y)\leq 2\cdot K(x)+O(1)+K(y)$
2. $K(x,y)\leq K(x)+K(y)+\Theta \left(\log(\min(K(x),K(y))\right)$

רמז: השתמש ברעיונות מתוךתרגיל: סיבוכיות מספרים טבעיים.