הבדלים בין גרסאות בדף "סיבוכיות"

קפיצה לניווט קפיצה לחיפוש
נוספו 80 בתים ,  לפני 10 שנים
מ
אין תקציר עריכה
מ (בוט מוסיף: no:Kompleksitetsteori)
מ
'''סיבוכיות''' (complexity) היא ענף של [[מדעי המחשב]] שבמסגרתו נבחנים המשאבים הנחוצים לפתרון בעיה נתונה באמצעות [[מחשב]], ומושווית יעילותם של [[אלגוריתם|אלגוריתמים]] שונים לפתרון בעיה זו. המשאב העיקרי הנבחן הוא '''[[סיבוכיות זמן|זמן הריצה]]''', כלומר נבחן משך הזמן הנחוץ לשם ביצוע האלגוריתם. משאב נוסף הוא ה'''[[סיבוכיות מקום|זיכרון]]''' הנחוץ לשם ביצוע האלגוריתם. ניתן להביא בחשבון משאבים נוספים, כגון כמה [[מעבד|מעבדים]] נחוצים לשם פתרון הבעיה ב[[עיבוד מקבילי]]. ענף הסיבוכיות נבדל מענף ה[[חישוביות]], שבו נבחנת השאלה האם ניתן בכלל לפתור בעיה נתונה, בלא קשר לכמות המשאבים הנחוצה.
 
==מאפייני הסיבוכיות==
 
'''בעיה''', בהקשר זה, היא [[קבוצה (מתמטיקה)|קבוצה]] של שאלות בעלות קשר הדוק. דוגמה: הבעיה [[פירוק לגורמים]] היא: כאשר נתון מספר שלם כלשהו, הצג את כל ה[[גורם ראשוני|גורמים הראשוניים]] שלו. שאלה ספציפית קרויה '''מופע''' של הבעיה. דוגמה: השאלה "הצג את הגורמים של המספר 15" היא מופע של בעיית הפירוק לגורמים.
 
==בעיות הכרעה==
חלק ניכר מתורת הסיבוכיות עוסק ב[[בעיית הכרעה|בעיות הכרעה]], שהן בעיות שבהן נדרשת התשובה הקצרה "כן" או "לא". דוגמה: הבעיה האם [[מספר טבעי]] נתון הוא [[מספר ראשוני]]. העניין בבעיות הכרעה נובע מכך שהטיפול המתמטי בהן הוא פשוט, שכן התשובה לבעיה מוגבלת ל"כן" ו"לא". עם זאת, בעיות שאינן בעיות הכרעה ניתנות להמרה בבעיות הכרעה שקולות.
 
דוגמה לכך היא הבעיה ''האם יש גורם ראשוני'': כאשר נתונים שני [[מספר שלםטבעי|מספרים שלמיםטבעיים]], n ו-k, ענה האם ל-n יש גורם ראשוני קטן מ-k. אם אנו מסוגלים לפתור את בעיית ההכרעה הזו באמצעות משאבים בסדר גודל מסוים, אנו יכולים לפתור את הבעיה "פירוק לגורמים", שאינה בעיית הכרעה, באמצעות משאבים מאותו סדר גודל, וזאת על ידי סדרה של שאלות התוחמות את ערכו האפשרי של k.
 
תורת הסיבוכיות מבחינה לעתים קרובות בין התשובה "כן" לתשובה "לא". דוגמה: הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת הבעיות שבהן התשובה "כן" ניתנת לבדיקה בזמן סביר. הקבוצה [[Co-NP]] היא קבוצת הבעיות שבהן התשובה "לא" ניתנת לבדיקה בזמן סביר. הקידומת Co היא קיצורה של המלה complement - משלים. המשלים של בעיה נתונה היא הבעיה שבה כל התשובות "כן" ו"לא" מוחלפות זו בזו. הבעיה "האם ראשוני" והבעיה "האם פריק" (מספר פריק הוא מספר שאינו ראשוני) משלימות זו את זו.
'''האם [[P=NP]]?'''
 
הקבוצה [[P (סיבוכיות)|P]] היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות [[מכונת טיורינג|מכונה]] דטרמיניסטית]] ב[[זמן ריצה פולינומי|זמן פולינומי]]. הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת כל בעיות ההכרעה שניתן לפתור אותן באמצעות [[מכונת טיורינג לא-דטרמיניסטית|מכונה לא דטרמיניסטית]] ב[[זמן ריצה פולינומי|זמן פולינומי]], או - לחליפין - לבדוק נכונות של פתרון נתון ב[[זמן ריצה פולינומי|זמן פולינומי]]. השאלה "האם הקבוצה [[P (סיבוכיות)|P]] שווה לקבוצה [[NP (סיבוכיות)|NP]]" היא השאלה המרכזית במדעי המחשב. זו שאלה פתוחה, [http://www.claymath.org/millennium/ [מכון קליי למתמטיקה]] מציע פרס של מיליון דולר לראשון שיפתור אותה.
 
ניתן יהיה להכריע בשאלה האם [[P=NP]] על ידי הכרעת השאלה האם יש ב-P בעיה [[NP-שלמה]] ב P.
 
מכונה דטרמיניסטית היא [[מכונת טיורינג]], או, לצורך הפשטות, מחשב רגיל, כזה המבצע את הוראות תוכנית צעד אחר צעד. מכונה לא דטרמיניסטית היא מכונה שבה ניתן לבצע גם הוראת התפצלות, שבה ביצוע התוכנית מתפצל למסלולים מקבילים, ודי שבאחד מהם תתקבל תשובה לבעיית ההכרעה. כל בעיה שניתן לפתור באמצעות מכונה לא דטרמיניסטית ניתן לפתור גם באמצעות מכונה דטרמיניסטית. במבט ראשון נוצר הרושם שמכונה לא דטרמיניסטית מהירה ממכונה דטרמיניסטית, בזכות המסלולים המקבילים שהיא מבצעת. עד כמה משמעותי ההבדל במהירויות של שתי המכונות? זו למעשה השאלה "האם הקבוצה P שווה לקבוצה NP". תשובה חיובית לשאלה זו פירושה שההבדל במהירויות אינו משמעותי.

תפריט ניווט