תורת החישוביות/שקילות מודלי חישוב/תרגילים

זיהוי פלינדרומים

1. תאר מ"ט בעלת שני סרטים המזהה פלינדרומים.
2. תאר מ"ט בעלת סרט אחד המזהה פלינדרום.
3. מה זמן הריצה של כ"א מהפתרונות שהצעת?

חסם לסיבוכיות זמן הריצה של מ"ט בעלת סרט יחיד

הנח שברשותך מ"ט בעלת $k$ סרטים הפותרת בעיה בגודל $n$ בזמן ריצה $f(n)$. מסמלצים את המכונה ע"י מכונה בעלת סרט יחיד כפי שמוצע בשקילות מ"ט מרובת סרטים. הראה שזמן הריצה הוא

$O(f(n{)}^2{k}^2)$