תרגיל 2 שאלה 2

6 views
Skip to first unread message

gilad green

unread,
Mar 5, 2011, 7:14:43 AM3/5/11
to Complexity סיבוכיות‎
הניסוח לא כ"כ ברור,
הכוונה היא להראות אלג שבהינתן אורקל של בעיית ההכרעה נותן פתרון לבעיית
החיפוש, נכון?

(המניסוח זה נשמע כאילו מחפשים הפוך- אבל זה קל מדי אז זה לא נשמע הגיוני)

ammar

unread,
Mar 6, 2011, 10:22:18 AM3/6/11
to Complexity סיבוכיות‎
בשאלה זאת האם יש צורך לכתוב את הוכחת הנכונות של הרדוקציה ?? אוו שזה
מספיק לכתוב אותה בלי הוכחה?

ishamor

unread,
Mar 6, 2011, 1:38:10 PM3/6/11
to Complexity סיבוכיות‎
למיטב הבנתי זאת הכוונה. בהינתן אוראקל לבעיית ההכרעה, הראה אלג'
פול' (כזה שעושה כמות פול' של חישובים ו/או קריאות לאוראקל) שפותר את
בעיית החיפוש.

ishamor

unread,
Mar 6, 2011, 1:42:57 PM3/6/11
to Complexity סיבוכיות‎
אני חושב שאם אתה מראה את האלגוריתם שפותר את בעיית ההכרעה תוך שימוש
באוראקל, הרי זו הוכחה של הרדוקציה. אלג' פול' כזה הוא הוכחה לקיום של
רדוקציית קוק פול'.
Reply all
Reply to author
Forward
0 new messages