קביעת הגבול בין זמן פולינומי לזמן אקספוננציאלי
נתונה מכונת טיורנג
M
נתון קלט
x
האם ניתן לדעת, בעת הרצת הקלט על המכונה, על ידי ספירת מספר הצעדים, אם הוא רץ בזמן פולינומי או אקספוננציאלי?
למשל, נניח כי אורך הקלט הוא 20. ומספר הצעדים במכונה עד הכרעתו הוא מיליון.
אז מצד אחד
20^4.6 =1,000,000
מצד שני
2^20 = 1,000,000
מנסה לשאול - האם כיצד ניתן לקבוע לאחר הרצת קלט בודד, מה יעילות הריצה?
