cc09b-a שאלה 3 ו-4

[Eugene]

מישהו יכול להסביר איך פותרים את שתי שאלות?

[Ran Zvilik]

בעיקרון את שתיהן אתה פותר ע"י סימלוץ המכונה M אבל עם הגבלות.

ההגבלה בשאלה השלישית היא שאתה לא עובר מקום מסויים בסרט (לינארית כאורך
הקלט) ולכן התשובה היא PSPACE.

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

מקווה שעזרתי ;)

[Eli Daian]

ולמה בשאלה 1 של אותו מבחן זה ב-NP?

בתאריך 24 ביוני 2010 09:19, מאת Ran Zvilik <rzv...@gmail.com>:

--
Eli Daian

[Ran Zvilik]

קבוצה ב"ת בגודל 4 אפשר לעשות בצורה לגוריתמית דטרמיניסטית לחלוטין (4
משתני לולאה כדי לעבור על כל הקבוצות של הצמתים
בגודל 4 בגרף ולבדוק אם הן אכן ב"ת(
אבל למצוא מסלול פשוט זו בעייה מורכבת יותר לעשות בזמן לגוריתמי:
למצוא מסלול שאורכו לכל היותר n/4
זו לא בעיה, כי פשוט מוצאים אם יש מסלול באורך כזה בין שני צמתים כלשהם,
ואם יש בו מעגלים מורידים אותם.
אבל מסלול באורך לפחות n/4 זו בעיה,
כי הטריק שהשתמשנו בו קודם כבר לא יעבוד כאן. נקודה מאוד מבלבלת כאן היא
הבעיה המשלימה, משום שיש כאלה שטועים וחושבים שהבעיה המשלימה לבעיה
שיש מסלול באורך לפחות היא שיש מסלול באורך לכל היותר. אבל זה או שיש
מסלול באורך לכל היותר גודל מסויים או שאין מסלול.

לכן, בהכרח המחלקה הקטנה ביותר שהבעיה שייכת אלייה היא NP

בהצלחה אלי :)

On Jun 24, 1:04 pm, Eli Daian <elida...@gmail.com> wrote:
> ולמה בשאלה 1 של אותו מבחן זה ב-NP?
>

> בתאריך 24 ביוני 2010 09:19, מאת Ran Zvilik <rzvi...@gmail.com>:

[Eli Daian]

תודה צוויליק :)
נקווה שיהיה טוב

בתאריך 24 ביוני 2010 13:43, מאת Ran Zvilik <rzv...@gmail.com>:

--
Eli Daian