תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרות: הגהה, עיצוב |
|||
שורה 14:
{{הגדרה|תוכן=
סיבוכיות קולומוגורוב <math>K(x)</math> של מחרוזת <math>x</math>, היא אורך הקידוד המינימלי של מכונה, שעל קלט ריק עוצרת עם הפלט <math>x</math>:{{רווח קשיח|2}}
<center><math>K(x) = \min_{M \;:\; M(\epsilon) = x} \left|\langle M \rangle\right| </math></center>
}}
לעתים
[[File:Flag of Ireland.svg|thumb|Flag of Ireland]]
▲[[File:Flag_of_Belgium_(civil).svg|thumb|Flag of Belgium (civil)]]
{{הגדרה|תוכן=
לכל שתי מחרוזת <math>x</math> ו<math>y</math>, '''הסיבוכיות המותנית''' <math>K(y|x)</math> של <math>y</math> בהנתן <math>x</math>
<center><math>K(y|x) = \min_{M \;:\; M(x) = y} \left|\langle M \rangle\right| </math></center>
כלומר, האורך המינימלי של קידוד מ"ט שעבור הקלט <math>x</math> פולטת את <math>y</math>.
}}
{{תרגיל|יישור=ימין
|שאלה=
#<math>K(xx) = K(x) + O(1)</math>
#<math>K(x|x) = O(1)</math>
|