שאלה ממבחן 03a
13 views
Skip to first unread message
itay
Jul 2, 2009, 12:40:30 PM7/2/09
to Complexity Course, Spring 2009, Tel Aviv University
לגבי השאלה
4. תהי C המחלקה הבאה:
L שייך C אם קיים verifier הסתברותי פולינומיאלי V כך ש:
אם x שייךL אז קיים עד y שאורכו פולינומיאלי ב- |x| כך ש: Prr[M(x,y,r)
=T] = 1
אם x שייך L אז לכל y שאורכו פולינומיאלי ב- |x| מתקיים Prr[M(x,y,r)=T]
<= 0.5
הוכיחו ש: BPP מוכל ב C.
4. תהי C המחלקה הבאה:
L שייך C אם קיים verifier הסתברותי פולינומיאלי V כך ש:
אם x שייךL אז קיים עד y שאורכו פולינומיאלי ב- |x| כך ש: Prr[M(x,y,r)
=T] = 1
אם x שייך L אז לכל y שאורכו פולינומיאלי ב- |x| מתקיים Prr[M(x,y,r)=T]
<= 0.5
הוכיחו ש: BPP מוכל ב C.
מישהו יודע האם אפשר לפתור את זה כשנשתמש במכונה לא דטרמינסטית עבור C ,
כלומר מכונה שתקבל עד
או שחייב להשתמש ב משפט שלמדנו בשיעור ש BPP מוכל ב PH??
yuval rochman
Jul 2, 2009, 12:43:04 PM7/2/09
to complexity-course-spring...@googlegroups.com
חייבים להשתמש בהוכחה שBPP מוכל בסיגמא 2
2009/7/2 itay <itay...@gmail.com>
Reply all
Reply to author
Forward
0 new messages