הבדלים בין גרסאות בדף "בעיית P=NP"

הוסרו 23 בתים ,  לפני שנתיים
מ (שינוי סדר הפרקים (בוט סדר הפרקים))
תגיות: עריכה ממכשיר נייד עריכה דרך האתר הנייד
==המחלקות P ו-NP==
{{הפניה לערך מורחב|ערכים=[[P (מחלקת סיבוכיות)]], [[NP (מחלקת סיבוכיות)]]}}
במדעי המחשב מוצעות מספר שיטות למדוד יעילות של [[אלגוריתם|אלגוריתמיים]] על בסיס הקלט שלו. הגישה הנפוצה היא למדוד את [[סיבוכיות זמן ריצה|זמן הריצה]] של האלגוריתם. על מנת למדוד את זמן הריצה בלי תלות במימוש האלגוריתם במחשב זה או אחר, נהוג למדוד את זמן הריצה על פי כמות הצעדים הבסיסיים שהאלגוריתם מבצע (ההגדרה המדויקת של "צעד בסיסי" מבוססת על [[מכונת טיורינג]]) .
 
מכיוון שקלטים גדולים יותר לבעיה גוררים לרוב זמן פתרון גדול יותר, זמן הריצה של האלגוריתם נמדד ביחס לאורך בקלט, לכמות הקלט או למורכבותו. אם ניתן לחסום את קצב גדילה של זמן הריצה של האלגוריתם עם גדילת הקלט על ידי [[פולינום]], אומרים כי האלגוריתם פותר את הבעיה ב[[זמן ריצה פולינומי]]. על פי רוב, זמן ריצה פולינומי נחשב לזמן ריצה סביר לצורך מימוש ביישומים מעשיים (ואף יותר מכך - זמן ריצה שאינו פולינומי נחשב לזמן ריצה שאינו סביר).