סיבוכיות קולמוגורוב – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ קטגוריה |
אין תקציר עריכה |
||
שורה 12:
==סיבוכיות קולמוגורוב והמושג 'מסובך'==
אחד הרעיונות מאחורי ההגדרה של סיבוכיות קולמוגורוב היא לתת הגדרה פורמלית למושג האינטואיטיבי 'מסובך', וניתן לשאול האם ההגדרה הזאת אכן מצליחה לבטא את מה שנתפס אצלנו בתור מסובך. למשל, ידוע שתוכנות פשוטות ביותר, הדורשות מספר קטן מאוד של שורות קוד, יכולות ליצור התנהגות מורכבת מאוד ומסובכת. באופן דומה בתחומים רבים בפיזיקה ובמתמטיקה, בעיקר במערכות [[פרקטל|פרקטליות]] ו[[כאוס|כאוטיות]] התנהגות מסובכת מאוד נוצרת מתוך חוקי בסיס פשוטים. בקריפטוגרפיה ידועים [[
למחרוזת ארוכה, שלא ניתן להבדיל, באופן אפקטיבי, בינה לבין מחרוזת אקראית (על סמך הנחות מקובלות). סיבוכיות קולמוגורוב של מחרוזות כאלה היא קטנה (תיאור הגרעין). לעומת זאת סיבוכיות קולמוגורוב של מחרוזת אקראית היא בהסתברות גבוהה כמעט כאורכה.
| |||