סיבוכיות – הבדלי גרסאות

נוספו 1,228 בתים ,  לפני חודשיים
(תשאר -> תישאר (דרך WP:JWB))
 
סוג נוסף של מדד סיבוכיות הוא [[סיבוכיות תקשורת]] המודדת את כמות המידע העוברת בין שני צדדים המשתתפים בפתרון בעיה.
 
==יישומים לבעיות עם סיבוכיות גבוהה==
כיום ידועות מספר בעיות שלא מוכר אלגוריתם יעיל הפותר אותן, אך בהינתן מידע נוסף הן ניתנות לפתרון יעיל, מה שפותח פתח לשימוש בבעיות אלו כבסיס למערכות הצפנה. הדוגמה הקלאסית היא של מערכת ה[[הצפנה]] [[RSA]], שבה כדי לפענח הודעה יש לבצע חישוב התלוי במספר שהוא מכפלת שני [[ראשוני]]ים גדולים. אם שני הראשוניים הללו ידועים קל לבצע את החישוב שמפענח הודעה; אך לא ידועה שום דרך לבצע חישוב זה ביעילות אם הם אינם ידועים, כך שקשה לתוקף לפצח את ההודעה (המתקפה הישירה ביותר דורשת [[פירוק לגורמים של מספר שלם|לפרק לגורמים]] את המכפלה, אך גם זוהי בעיה שנחשבת כיום לקשה). באופן כללי פונקציות שקל לחשב אך קשה להפוך מבלי שיהיה נתון מידע נוסף נקראות "פונקציות מלכודת" (Trapdoor functions).
 
==ראו גם==