 |
ליתר דיוק: השאלה שבאמת מעניינת אותנו היא לא "האם אפשר להבחין17 בין הפלט הזה לבין רעש אקראי?" אלא "האם אפשר להבחין17 בין הפלט הזה לבין רעש אקראי בזמן סביר?".
המושג התאורטי (שוב: תאורטי. לא מעשי. אבל במקרה הזה כבר יש לו קשר למציאות) המקובל לגבי "זמן סביר" הוא זמן ריצה פולינומי. כלומר זמן הריצה גדר רק כפונקציה פולינומית של N ולא משהו יותר גרוע מהסוג של פונקציה מעריכית. ר' לדוגמה חישוב יעיל [ויקיפדיה].
באמת קל לראות23 שיש דרך פשוטה אך עם זמן ריצה מעריכי להבדיל בין הפלט של האלגוריתם שלנו לבין רעש אמיתי (עם כמה הנחות סבירות על האלגוריתם שלנו).
17 בהסתברות גבוהה מספיק. לדוגמה: יש לנו מבחן שתופס רצף לא אקראי בהסתברות מסדר גודל של חצי ואחנו יכולים לחזור עליו בצורה בלתי־תלויה (כלומר: כשנחזור עליו שוב ההסתברות לתפוס רצף לא אקראי היא שוב מהסתברות חצי. ע"י מספיק חזרות אנחנו יכולים לקבל הסתברות טובה כרצונינו.
23 בעברית: שיעורי בית
|
 |
RSS מאמרים |
כתבו למערכת |
אודות האתר |
טרם התעדכנת |
ארכיון |
חיפוש |
עזרה |
תנאי שימוש