בעיות 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 היא סדרת הצעדים שגורמת למכונה הלא דטרמיניסטית לעצור.