תורת הסיבוכיות – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
Matanyabot (שיחה | תרומות) מ בוט החלפות: לעיתים |
מאין תקציר עריכה |
||
שורה 18:
מכונה דטרמיניסטית היא [[מכונת טיורינג]], או, לצורך הפשטות, מחשב רגיל, כזה המבצע את הוראות תוכנית צעד אחר צעד. מכונה לא דטרמיניסטית היא מכונה שבה ניתן לבצע גם הוראת התפצלות, שבה ביצוע התוכנית מתפצל למסלולים מקבילים, ודי שבאחד מהם תתקבל תשובה לבעיית ההכרעה. כל בעיה שניתן לפתור באמצעות מכונה לא דטרמיניסטית ניתן לפתור גם באמצעות מכונה דטרמיניסטית. במבט ראשון נוצר הרושם שמכונה לא דטרמיניסטית מהירה ממכונה דטרמיניסטית, בזכות המסלולים המקבילים שהיא מבצעת. עד כמה משמעותי ההבדל במהירויות של שתי המכונות? זו למעשה השאלה "האם הקבוצה P שווה לקבוצה NP". תשובה חיובית לשאלה זו פירושה שההבדל במהירויות אינו משמעותי.
[[קובץ:Complexity classes-he.png|300px|לא ממוסגר]]
==קישורים חיצוניים==
| |||