מהו זמן הפולינום הלא-דטרמיניסטי (np)? - הגדרה מטכנולוגיה

הגדרה - מה המשמעות של זמן פולינומי לא-דטרמיניסטי (NP)?

זמן פולינומי לא-דטרמיניסטי (NP) הוא למעשה סמן המשמש להצביע על מערכת של בעיות וגבולות היכולת של סוגים מסוימים של מחשוב. NP מתייחס למערכת הבעיות הניתנות לפיתרון בזמן פולינומי על ידי מכונת טיורינג לא דטרמיניסטית.

Techopedia מסביר זמן פולינומי לא-דטרמיניסטי (NP)

זמן פולינום לא-דטרמיניסטי מבוסס על הביטוי "זמן פולינום", המתייחס אם אלגוריתם יכול לבצע גבולות מסוימים הרלוונטיים למהירות. זמן הפולינומי התגלה כדרך לדבר על היתכנות של עבודת ופיתוח אלגוריתמים.

אם הבעיה נמצאת בזמן פולינום לא-דטרמיניסטי, מכונת טיורינג הלא-דטרמיניסטית יכולה תחילה לנחש מה הפיתרון, ואז להריץ אלגוריתם שניתן לאמתו שיאשר אם הניחוש הזה היה נכון. תוכניות הגדרה מבוססות-אימות או הגדרת מכונה יבחנו במהותן את הבחירות הראשוניות של מכונת הטיורינג הלא-דטרמיניסטית לאימות התוצאות.

כל זה הוא מבנה מחשוב תיאורטי ביותר. בעוד שלמידת מכונות עושה דרכים מעבר למערכות דטרמיניסטיות, הרעיון לאמת בחירות לא-דטרמיניסטיות עדיין נמצא בחיתוליו. חפש פיתוח נוסף בגבול המחשוב הזה.