ויקיספר

תורת החישוביות/סיבוכיות קולמוגורוב/הסתברות אוניברסאלית: הבדלים בין גרסאות בדף

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
Atavory (שיחה | תרומות)
7,521 עריכות
Atavory (שיחה | תרומות)
7,521 עריכות
שורה 38:
}}
 
 
נניח ש-<math>M_K(x)</math> היא התוכנית הקצרה ביותר המייצרת את <math>x</math>. אז
 
בשאר החלק נוכיח את שני הכוונים של משפט זה.
שורה 47 ⟵ 45:
===סיבוכיות קולמוגורוב היא לכל הפחות סיבוכיות אוניברסאלית===
 
כוון זה קל להוכיח. הדבר נובע למעשה מההגדרה:. נניח ש-<math>M_x^K</math> היא התוכנית הקצרה ביותר המייצרת את <math>x</math>. אז
<center><math>
P_K(x) = \left| \Sigma \right|^{- K(x)} = \left| \Sigma \right|^{- \left| \langle M_K(x)M_x^K \rangle\right|} \leq
\sum_{M \;|\; M(\epsilon) = x} \left| \Sigma \right|^{- \left| \langle M \rangle \right|} =
P_u(x).
אוחזר מתוך "https://he.wikibooks.org/wiki/תורת_החישוביות/סיבוכיות_קולמוגורוב/הסתברות_אוניברסאלית"