תורת החישוביות/סיבוכיות קולמוגורוב: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
הרחבה |
מ תקלדה |
||
שורה 9:
בפרק זה נגדיר רעיון זה במדוייק בעזרת [[תורת_החישוביות/מכונת_טיורינג_אוניברסלית|מ"ט אוניברסליות]]. רעיון זה מקשר בין תחום החישוביות לתחומים אחרים, כגון [[w:תורת האינפורמציה|תורת האינפורמציה]], ויש לו מספר שימושים. ב[[#הגדרות|הגדרות]] נגדיר את [[w:סיבוכיות הקולמוגורוב]] של מחרוזת כאורך הקצר ביותר של מ"ט המייצרת אותה.
ב[[#אי-חישוביות פונקציית הסיבוכיות|אי-חישוביות פונקציית הסיבוכיות]] נראה שפונקציה זו איננה נתנת לחישוב, אך ב[[#אי-דחיסות מחרוזות|אי-דחיסות מחרוזות]] נראה שלרוב המחרוזות יש סיבוכיות קולמוגורוב קרובה למדי לאורכן המקורי. זו טענה קומבינטורית חזקה למדי, לפיה אי אפשר לדחוס מחרוזות. ב[[#יישום: חסמים תחתונים לסיבוכיות אלגוריתמים|יישום: חסמים תחתונים לסיבוכיות אלגוריתמים]] ו[[#יישום: אורך רצפים בסדרות בינאריות רנדומיות|יישום: אורך רצפים בסדרות בינאריות רנדומיות]], נראה כיצד לנצל טענה קומבינטורית חזקה זו. לבסוף, ב[[#כלל השרשרת לסיבוכיות|כלל השרשרת לסיבוכיות]], נדון קצת יותר בסיבוכיות תיאור מחרוזת בהנחה שאחרת כבר תוארה.
==הגדרות==
| |||