שיחה:תורת החישוביות/סיבוכיות קולמוגורוב

איך מגדירים

לא ברור לי הצורך במ״ט אוניברסלית. הקידוד של M קבוע (לפי תורת החישוביות/מכונת טיורינג אוניברסלית), ומרגע שזה קבוע, כל שתי מ״ט אוניברסליות U ו U' מתנהגות זהה על אותו הקידוד. מציע לשנות להגדרה ה"ישירה". ‏gran‏ - שיחה 04:04, 28 בינואר 2012 (IST)

מעולם לא ראיתי ספר לימוד שעשה זאת, ואני חושב שישנה הנחה מובלעת בדבריך. אינטואיטיבית, זה נועד לטפל באמירות כמו "תכניות fortran קצרות יותר מאלו בC עבור בעיות נומריות". אפשר לחשוב על הרחבות פשוטות לא"ב ולמ"ט אוניברסליות, לפיהן, נניח, הפונקציה "סינוס" היא פרימיטיב של השפה. מה שהמשפט אומר הוא שיש מגבלה לתועלת הדברים הללו מבחינת הדחיסות. מסכים שהנקודה העיקרית היא להפטר מזה כמה שיותר מהר. Atavory - שיחה 10:38, 28 בינואר 2012 (IST)

כנ״ל בהגדרת הסיבוכיות המותנית: מספר המצבים המינימלי של מ”ט אשר על קלט x עוצרת עם הפלט y. עדיף גם להעביר את ההגדרה הזו אחרי הפרק של אי־חישוביות K, שהיא-היא עיקר הפרק הזה (הנושא העיקרי של הספר הוא: מה חשיב ומה לא..) ‏gran‏ - שיחה 04:18, 28 בינואר 2012 (IST)

אין לי התנגדות אם יש לך העדפה לכך. Atavory - שיחה 10:38, 28 בינואר 2012 (IST)

מה שקיים כרגע פשוט לא עקבי עם תחילת הספר: אם U וU' מ״ט אוניברסליות, אז פעילותן על הקידוד של M הוא זהה, לכן $K_{U}=K_{U'}$. אם אתה רוצה לתת הגדרה יותר רחבה של הסיבוכיות, אז קודם אתה צריך להרחיב את מושג הקידוד בהתאם. ‏gran‏ - שיחה 03:55, 29 בינואר 2012 (IST)

טוב, נראה לי שאמחק ואעביר זאת לתרגיל. Atavory - שיחה 09:51, 29 בינואר 2012 (IST)

אוקיי, כעת עקבי עם שאר הספר. נראה לי אכן שכדאי להוסיף זאת כתרגיל, מפני שמנסיון, אנשים לא יודעים זאת לגבי שפות תכנות, לדוגמה. היו מספר שינויים שגרמו לחוסר עקביות עם שאר הפרק. אין לי התנגדות רבה אליהם, אך אם עושים אותם, צריך לעשותם גם באופן עקבי בשאר. מדובר הן בסימון המודגש לK, והן בשאלה האם המחרוזות בינאריות או לא (לכל הפחות, צריך להחליף הרבה מהנוסחאות בהמשך הפרק). אחת הטענות גם הופיעה בהגדרות לפני מקומה בהמשך הדף. Atavory - שיחה 20:43, 29 בינואר 2012 (IST)

יישומים

הייתי מעביר את כל היישומים (ושאר הדברים שאינם "הרד-קור תורת החישוביות" לתת-פרק של סיבוכיות קולמוגורוב (דף נפרד), ושם "שקול לדלג" ענקי בראש הפרק. ‏gran‏ - שיחה 04:14, 28 בינואר 2012 (IST)

אם ממש אתה רוצה, אפשר. לטעמי, ללא הדברים הללו או יישום אחר, נניח הסתברות אוניברסלית, קשה מאד להבין בשביל מה צריך את זה בכלל. זה שונה מנושא החישוביות בכללותו, בו יש מוטיווציות מאד ברורות (אי אפשר לכתוב מספר כלי ווריפיקציה אוטומטית, לדוגמה - זה סותר משפטים שונים). אגב, אם ממשיכים את ההגיון שלך כאן, אנא ראה את השיחה בעמוד הראשון של ספר זה לגבי P ו NP‏. Atavory - שיחה 10:38, 28 בינואר 2012 (IST)

אני חושב שכדאי. ‏gran‏ - שיחה 03:55, 29 בינואר 2012 (IST)

אוקיי. Atavory - שיחה 10:03, 3 בפברואר 2012 (IST)

בעיה בהגדרה

עשיתי קצת שינויים, ושמתי לב שההוכחה של "קיים קבוע c שעבורו, לכל מחרוזת x, $K(x)\leq |x|+c$" לא מדוייקת כרגע, אולי באשמת שינוי ההגדרה ממ״ט אוניברסליות לאורך קידוד. אם מגדירים את הסיבוכיות כמספר המצבים של מ״ט, אז ברור שהמשפט נכון, והקבוע הוא $c=1$. אבל כפי שמוגדר כרגע, צריך להראות שהקידוד לא משתנה הרבה. כנראה שצריך לשנות את ההוכחה כך שתשתמש במ״ט אוניברסלית. משום מה אני לא רואה פתרון ישיר. ‏gran‏ - שיחה 06:49, 4 בפברואר 2012 (IST)

אהלן,

מסכים (חלקית). אפילו יותר מזה: לדעתי גם החזרה למ"ט אוניברסאלית לא תפתור את העניינים, משום שלפי הגדרתה המקובלת (אולי לפי ספר זה ואולי לא), אם היא מקבלת מחרוזת שאינה תיאור מ"ט, היא דוחה/עוצרת/וכו'.

לכאורה אפשר להפוך את הכל למדוייק בזה שנגדיר מ"ט אוניברסאלית במובן מוכלל יותר: היא מניחה שמה שהיא קיבלה הוא תיאור מ"ט, וממשיכה לפעול כל עוד אפשר. זה היה מאפשר, לדוגמה, "להחביא" data-segment בתוך תיאור המ"ט. אולי לא מדובר במ"ט תקנית, אך המכונה האוניברסאלית היתה יכולה להריץ את זה.

לטעמי מאד כדאי להמנע מכוון זה. זה, לדעתי, מראה את הבדלי ה"ראש" בין נושאים שונים במדעי המחשב. חישוביות hard-core מוגדרת לגמרי בעזרת מ"ט. כשמגיעים לרדוקציות NP, הגיוני (תחת הנחות סבירות) להניח שיש שפה כלשהי בה אפשר לתאר גראפים וכו'. סיבוכיות קולמוגורוב היא "על התפר": מצד אחד היא קשורה לאי-חישוביות, ומצד שני הרדוקציות בה (לדוגמה בחלק יישומי אי-דחיסות) מסורבלות להפליא ממש במ"ט.

לכן, הייתי מציע את הדבר הבא. בראש הפרק, כדאי לציין שבוחרים שפה מלאה (במובן Church Turing) ובפרק זה, משמעות $M(\epsilon )$ היא פונקציה נטולת-פרמטרים בשפה זו. מוסיפים עוד תרגיל שמראה שההבדל הוא עד כדי קבוע חיבורי, ושלום על ישראל. עדיין יש קשר חזק לקורס (השערת צ"ט, שימוש בבעיית העצירה), אבל הסימונים חופשיים יותר לצורך השפיות. מה דעתך?

Atavory - שיחה 11:31, 4 בפברואר 2012 (IST)

זה נראה לי ממש מוזר. אני לא מצליח להוכיח שקילות בין שתי ההגדרות (זו של מספר מצבים וזו של אורך קידוד). חשבתי שהן נבדלות בקבוע אדיטיבי, אבל פתאום נראה לי שהקבוע הוא כפלי. אני לא מכיר את הנושאים האלה לעומק, אבל מה שתארת מרגיש כמו "רמאות" במובן שאנחנו מספקים קלט לפונקציה, ואז למעשה מדובר על הסיבוכיות המותנית (בהנתן אותו הקלט) ולא על סיבוכיות הקולמוגורוב עצמה. מעניין איך סיפסר מגדיר (אני אבדוק בהמשך השבוע אם תרצה). כשאמרתי, אני לא בקיא בנושא יותר מדי, לכן כל פתרון נאות מתמטית מקובל עלי, עם העדפה לפתרונות כמה שיותר פשוטים - שיעבירו את המסר המתאים מקורס בסיסי זה (להבדיל מקורס מתקדם). ‏gran‏ - שיחה 03:41, 5 בפברואר 2012 (IST)

אינני חושב שבקורסים מתקדמים יותר בתחום נהיים יותר פורמאליים לגבי ההגדרה הבסיסית, אלא להיפך. הספר של Vitanyi וLee, לדוגמה, שלדעתי הוא די state of the art כספר לימוד לנושא זה, די מנפנף מהר את ההגדרות, וחופשי למדי בשימושים לאחר מכן.

עכ"פ, סידרתי שוב את נושא ההגדרות. נראה לי שחשוב להגיע לאיזון בין: עקביות בספר זה, עקביות לגבי הנושא מחוץ לספר זה, ומובנות. אני מקווה שהפתרון הנוכחי עומד בזה. Atavory - שיחה 12:12, 5 בפברואר 2012 (IST)

האם ההגדרה הנוכחית של $K^{TM}$ הגיונית? נראה לי שלכל x מתקיים $K^{TM}(x)=c$, לא? ‏gran‏ - שיחה 08:10, 12 בפברואר 2012 (IST)

אינני מבין. איך אפשר לבטא , נניח $|\Sigma |^{2c}$ מחרוזות בעזרת $c$ סיבולים? Atavory - שיחה 09:59, 12 בפברואר 2012 (IST)

לא דייקתי.. כוונתי הייתה שמכיוון שהוגדר $\min _{M,w\;:\;M(w)=x}\left|\langle M\rangle \right|+\left|w\right|$ אזי עבור מחרוזת x, המינימות מתבצע גם על המחרוזת x, ולכן עם מכונה ריקה אפשר לייצר את x.. אבל במחשבה שניה המשמעות היא שלכל x מתקיים $K^{TM}(x)\leq |x|$.. פשוט ההגדרה הזו לא היתה אינטואיטיבית עבורי. ‏gran‏ - שיחה 22:14, 12 בפברואר 2012 (IST)