תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
מ ←הגדרות: הגהה - עקביות עם שאר הספר, ביטול חוסר עקביות עם שאר הפרק. |
←הגדרות: כנראה לכך הכוונה |
||
שורה 12:
{{הגדרה|תוכן=
סיבוכיות קולומוגורוב <math>K(x)</math> של מחרוזת <math>x</math>, היא
<center><math>K(x) = \min_{M \;:\; M(\epsilon) = x} \left|\langle M \rangle\right| </math></center>
}}
שורה 24:
לכל שתי מחרוזת <math>x</math> ו<math>y</math>, '''הסיבוכיות המותנית''' של <math>y</math> בהנתן <math>x</math> היא
<center><math>K(y|x) = \min_{M \;:\;
כלומר, תיאור מ"ט הקצרה ביותר
}}
| |||