שיחה:סיבוכיות קולמוגורוב
יריית פתיחה עריכה
מה שכתבתי זו רק ירייה מהמותן. הנושא מרתק ומשווע לויקפדים שירחיבו אותו. הערך המקביל באנגלית נראה לא רע. 
אורי מוסנזון 22:11, 10 ינו' 2005 (UTC)
פסקת הביקורת אינה ברורה לי עריכה
אינני מבין מאומה בנושא של סיבוכיות קולמוגורוב, אבל נראה לי שהביקורת מבצעת כמה קפיצות לוגיות. בפרט, במשפט "ישנם מערכות שלמרות שניתן להגדיר אותם בקלות (ולכן על-פי ההגדרה של קולמוגורוב הם אינם מסובכים) מראות התנהגות סבוכה".
המושג "בקלות" כאן לא מוגדר היטב ולא ברורה משמעותו. המשמעות של "בקלות" כאן יכולה וחייבת להיות יחסית; דהיינו, צריך להראות שהמערכות הללו אכן ניתנות להגדרה שהיא קצרה יותר באופן משמעותי מהגדרה של מערכות שמראות התנהגות פשוטה יותר. כרגע המשפט לכל היותר אומר "מערכות שנראות לנו מסובכות הן בעלות סיבוכיות קולמוגורוב שנראית נמוכה באופן אבסולטי", אבל הרי כל הרעיון פה הוא בסיבוכיות היחסית.
שנית, הביקורת כאן היא רק על הטענה "סיבוכיות קולמוגורוב מתארת את מה שאנחנו מבינים באופן אינטואיטיבי כ"מסובך". לא ראיתי שמישהו טען טענה כזו בערך, ולא ברור אם זו המשמעות שאכן מיוחסת היכן שהוא לסיבוכיות קולמוגורב. לכן לא ברור כנגד מה באים הטיעונים שכנגד. גדי אלכסנדרוביץ' - שיחה 18:18, 27 במאי 2008 (IDT)
- אהלן! התקשתי קצת עם הניסוח אבל הפואנטה היא זו: השאיפה מאחורי סיבוכיות קולמוגורוב היא לתת הגדרה פורמלית למושג האינטואיטיבי 'סיבוך'. הפיסקה ממחישה את העובדה שההגדרה לא מצליחה לגמרי בכך, מכיוון שגם תוכנות מחשב פשוטות יכולות ליצור דברים שנראים לנו כמסובכים מאוד. אשמח אם תוכל לשפר את הניסוח הקלוקל. טוקיוני 18:27, 27 במאי 2008 (IDT)
- כאמור, הכשל (בהעברת הביקורת - איני טוען שהיא שגויה או שאתה טיפש) הוא כפול - ראשית, הוא מייחס למושג הפורמלי שהוצג קודם "שאיפה" - זה לא מספיק. יש להבהיר מי בדיוק שואף לזה ואיך זה בא לידי ביטוי בפועל בשימושים של הסיבוכיות. שנית, "גם תוכנות פשוטות יכולות ליצור דברים מסובכים" לא סותר בכלל את ההגדרה של הסיבוכיות, שהיא כאמור יחסית; אולי אפשר ליצור כל דבר באמצעות תוכנית פשוטה? אולי מה שאי אפשר ליצור עם תוכנית פשוטה הוא הרבה יותר מסובך מהדברים המסובכים שכן אפשר ליצור עם תוכנית פשוטה? חייבים להביא את קני המידה המתאימים - למשל, הדגמה של מחרוזת ש"נראית" לנו פשוטה אבל קיימת הוכחה שסיבוכיות הקולמוגורוב שלה גדולה מהותית (דהיינו, בסדרי גודל ולא בקבוע - כי אחרת אנחנו סתם משתעשעים עם בחירת המודל) מזו של המחרוזות ה"מסובכות" שציינת. גדי אלכסנדרוביץ' - שיחה 22:15, 27 במאי 2008 (IDT)
- יותר טוב? טוקיוני 13:07, 28 במאי 2008 (IDT)
- ההשקעה שלך ראויה להערכה, אבל אני לא חושב שהשינוי שביצעת מהותי - הבעיות שציינתי עדיין קיימות. למשל - כשאתה אומר ש"אחד מהרעיונות הוא..." אתה צריך להבהיר מי טוען את הטענה הזו ואיך זה בא לידי ביטוי מעשי. אחרת, ה"ביקורת" היא על איש קש. גדי אלכסנדרוביץ' - שיחה 14:25, 28 במאי 2008 (IDT)
- לא ירדתי לסוף דעתך, ובכל אופן אני מושך את ידי מפה. כל הכבוד לאלגורתמיקאי על התוספות. טוקיוני 18:24, 28 במאי 2008 (IDT)
- אם אלגורתמיקאי הוא מי שאני חושב שהוא, קטונתי, ובכל זאת - התוספת אומרת שבקריפטוגרפיה ידועים מחוללים פסאודו אקראיים; אם המרצה שלי לקריפטוגרפיה תיאורטית לא שיקר לי שלשום (ואולי הוא שיקר), לא רק שכרגע לא ידוע על אף מחולל פסאודו אקראי מוכח, אלא אף קיום של כזה יגרור ש-P שונה מ-NP, כך שהשימוש בהם בתור דוגמה הוא קצת בעייתי. גדי אלכסנדרוביץ' - שיחה 23:10, 28 במאי 2008 (IDT)
- המרצה שלך לא שיקר, והוספתי הבהרה. אלגוריתמיקאי - שיחה 18:47, 29 במאי 2008 (IDT)
- אם אלגורתמיקאי הוא מי שאני חושב שהוא, קטונתי, ובכל זאת - התוספת אומרת שבקריפטוגרפיה ידועים מחוללים פסאודו אקראיים; אם המרצה שלי לקריפטוגרפיה תיאורטית לא שיקר לי שלשום (ואולי הוא שיקר), לא רק שכרגע לא ידוע על אף מחולל פסאודו אקראי מוכח, אלא אף קיום של כזה יגרור ש-P שונה מ-NP, כך שהשימוש בהם בתור דוגמה הוא קצת בעייתי. גדי אלכסנדרוביץ' - שיחה 23:10, 28 במאי 2008 (IDT)
- לא ירדתי לסוף דעתך, ובכל אופן אני מושך את ידי מפה. כל הכבוד לאלגורתמיקאי על התוספות. טוקיוני 18:24, 28 במאי 2008 (IDT)
- ההשקעה שלך ראויה להערכה, אבל אני לא חושב שהשינוי שביצעת מהותי - הבעיות שציינתי עדיין קיימות. למשל - כשאתה אומר ש"אחד מהרעיונות הוא..." אתה צריך להבהיר מי טוען את הטענה הזו ואיך זה בא לידי ביטוי מעשי. אחרת, ה"ביקורת" היא על איש קש. גדי אלכסנדרוביץ' - שיחה 14:25, 28 במאי 2008 (IDT)
- יותר טוב? טוקיוני 13:07, 28 במאי 2008 (IDT)
- כאמור, הכשל (בהעברת הביקורת - איני טוען שהיא שגויה או שאתה טיפש) הוא כפול - ראשית, הוא מייחס למושג הפורמלי שהוצג קודם "שאיפה" - זה לא מספיק. יש להבהיר מי בדיוק שואף לזה ואיך זה בא לידי ביטוי בפועל בשימושים של הסיבוכיות. שנית, "גם תוכנות פשוטות יכולות ליצור דברים מסובכים" לא סותר בכלל את ההגדרה של הסיבוכיות, שהיא כאמור יחסית; אולי אפשר ליצור כל דבר באמצעות תוכנית פשוטה? אולי מה שאי אפשר ליצור עם תוכנית פשוטה הוא הרבה יותר מסובך מהדברים המסובכים שכן אפשר ליצור עם תוכנית פשוטה? חייבים להביא את קני המידה המתאימים - למשל, הדגמה של מחרוזת ש"נראית" לנו פשוטה אבל קיימת הוכחה שסיבוכיות הקולמוגורוב שלה גדולה מהותית (דהיינו, בסדרי גודל ולא בקבוע - כי אחרת אנחנו סתם משתעשעים עם בחירת המודל) מזו של המחרוזות ה"מסובכות" שציינת. גדי אלכסנדרוביץ' - שיחה 22:15, 27 במאי 2008 (IDT)
לא מבינה! עריכה
אני מצטטת: "לדוגמה, ניתן להוכיח באמצעותו גרסה חלשה של משפט המספרים הראשוניים במספר שורות." להוכיח מה בדיוק? מישהו יכול לתרגם לי את המשפט הזה לעברית, בבקשה? קסניה שיינרמן 89.138.204.225 10:35, 13 באוגוסט 2008 (IDT)
- יש הסבר על משפט המספרים הראשוניים בלינק ובו מוזכרות גרסאות חלשות יותר. כלומר סיבוכיות קולמוגרוב מאפשרת הוכחה קצרה של של משפט שהוא גרסה חלשה של משפט המספרים הראשוניים. אלגוריתמיקאי - שיחה 11:04, 13 באוגוסט 2008 (IDT)
לא הבנת. אני מתכוונת לכך שמבחינה תחבירית המשפט אשר ציטטתי אינו ברור. קסניה שיינרמן 89.138.204.225 11:15, 13 באוגוסט 2008 (IDT)
בעצם, הסתדרתי. הפסוקית "במספר שורות" מתייחסת ל "ניתן להוכיח" ולא ל "משפט המספרים הראשוניים". תודה. קסניה שיינרמן 89.138.204.225 11:19, 13 באוגוסט 2008 (IDT)