» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
הגדרת בעיות P ו- NP
דף ראשי  ממשיכים לאלגוריתמים 2  הגדרת בעיות P ו- NP גרסה להדפסה

בעיות P ו-NP - הגדרה

 

הגדרה: תהי: f:N→N . נגדיר: { L בעלת סיבוכיות זמן f| L}=DTIME(f)

 

הגדרה: האוסף P הינו האוסף P=U DTIME(f) (f פולינום).

אוסף כל השפות שאפשר להכריע אותם בסיבוכיות זמן פולינומית.

 

הגדרה: תהי M מ"ט לא דטרמיניסטית, ותהי f:N→N .

נאמר כי M פועלת בסיבוכיות זמן f אם לכל xε∑* , אם קיים חישוב של M שעוצר על x,

אזי קיים חישוב של M שעוצר על x בלכל היותר f(|x|) צעדים.

 

הגדרה: תהי L שפה. נאמר כי L בעלת סיבוכיות זמן לא דטרמיניסטית f

אם קיימת מ"ט לא דטרמיניסטית M שמקבלת את L , ו-M פועלת בסיבוכיות זמן f.

 

הגדרה: תהי: f:N→N . נגדיר:

 { L בעלת סיבוכיות זמן לא דטרמיניסטית f| L}=NTIME(f)

 

הגדרה: NP=U NTIME(f)

כל השפות שיש להן מ"ט לא דטרמיניסטית שמקבלת אותן בזמן פולינומי.

הגדרה שקולה ל-NP:

תהי L שפה. נאמר כי L הינה ב-NP אם קיימת מ"ט דטרמיניסטית R שמקבלת שני קלטים:x,y שפועלת בסיבוכיות זמן פולינומית, כך שמתקיים: לכל xε∑*:

1)       אם x ב-L אזי קיים y כך ש: |y|≤f(|x|), R(x,y) עוצרת.

2)       אחרת, לכל y R(x,y) לא עוצרת.

 

y היא סדרת הצעדים שגורמת למכונה הלא דטרמיניסטית לעצור.

 

 21-01-04 / 20:23  נוצר ע"י שמרית דויטש  בתאריך 
 הגדרת סיבוכיות - הקודםהבא - מבחן מסכם 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 7