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

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

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

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

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

הוכח שמתקיים

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

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

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

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

1. $K(x,y)\le 2\cdot K(x)+O(1)+K(y)$
2. $K(x,y)\le K(x)+K(y)+\mathrm{\Theta }(\log (\min (K(x),K(y)))$

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