ויקיפדיה

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

עיון אינטראקטיבי בהיסטוריה
→ העריכה הקודמתהעריכה הבאה ←
תוכן שנמחק תוכן שנוסף
חזותיקוד ויקי
מ שוחזר מעריכות של 109.186.25.111 (שיחה) לעריכה האחרונה של Uziel302
Matanyabot (שיחה | תרומות)
475,756 עריכות
מ בוט החלפות: לעיתים
שורה 8:
דוגמה לכך היא הבעיה ''האם יש גורם ראשוני'': כאשר נתונים שני [[מספר טבעי|מספרים טבעיים]], n ו-k, ענה האם ל-n יש גורם ראשוני קטן מ-k. אם אנו מסוגלים לפתור את בעיית ההכרעה הזו באמצעות משאבים בסדר גודל מסוים, אנו יכולים לפתור את הבעיה "פירוק לגורמים", שאינה בעיית הכרעה, באמצעות משאבים מאותו סדר גודל, וזאת על ידי סדרה של שאלות התוחמות את ערכו האפשרי של k.
 
תורת הסיבוכיות מבחינה לעתיםלעיתים קרובות בין התשובה "כן" לתשובה "לא". דוגמה: הקבוצה [[NP (סיבוכיות)|NP]] היא קבוצת הבעיות שבהן התשובה "כן" ניתנת לבדיקה בזמן סביר. הקבוצה [[Co-NP]] היא קבוצת הבעיות שבהן התשובה "לא" ניתנת לבדיקה בזמן סביר. הקידומת Co היא קיצורה של המלה complement - משלים. המשלים של בעיה נתונה היא הבעיה שבה כל התשובות "כן" ו"לא" מוחלפות זו בזו. הבעיה "האם ראשוני" והבעיה "האם פריק" (מספר פריק הוא מספר שאינו ראשוני) משלימות זו את זו.
 
'''האם [[P=NP]]?'''
אוחזר מתוך "https://he.wikipedia.org/wiki/תורת_הסיבוכיות"