תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרות: הגהה, עיצוב |
←אי-דחיסות מחרוזות: בעיה. |
||
שורה 75:
==אי-דחיסות מחרוזות==
למרות שלא קיים אלגוריתם (מ״ט) שמחשב את סיבוכיות הקולמוגורוב של כל מחרוזת נתונה, קיימים מספר חסמים על סיבוכיות זו.
קל לראות, שהסיבוכיות של מחרוזת <math>x</math> לא תהיה גדולה בהרבה מאורך המחרוזת עצמה.
{{טענה|תוכן=▼
קיים קבוע <math>c</math> שעבורו, לכל מחרוזת <math>x</math>,{{רווח קשיח|2}}▼
<math>K(x) \leq |x| + c</math>▼
}}▼
{{הוכחה|1=▼
למרות שאי אפשר לחשב את סיבוכיות הקולמוגורוב של סדרה, קיימות מחרוזות שסיבוכיות הקולמוגורוב שלהן איננה קטנה יותר מארכן.▼
ברור
<math>M(x) = x </math>. כעת נוכל לתאר כל מחרוזת <math>x</math> בעזרת ▼
<math>\langle M \rangle </math> שלאחריה משורשר <math>x</math>. ▼
}}▼
▲
{{משפט
|שם=קיום מחרוזות אי-דחיסות
שורה 122 ⟵ 136:
(הוכחת המשפט נמצאת ב[[תורת החישוביות/סיבוכיות קולמוגורוב/תרגילים#רוב המחרוזות אינן דחיסות במיוחד|תרגיל: רוב המחרוזות אינן דחיסות במיוחד]].)
נשים לב שמשמעות הביטוי היא ש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>x</math> בעזרת
▲<math>\langle M \rangle </math> שלאחריה משורשר <math>x</math>.
▲}}
==כלל השרשרת לסיבוכיות==
|