BPP - the minimal size of beta
Tom
BPP
חייב להיות גדול מחצי, או שכל שבר גדול מאפס ושגם גדול מאלפא בשבר שהוא
לפחות פולינומי מספיק?
כלומר, אם
beta = x + 1/poly(n)
alpha = x
מה הגודל המינמלי של
x
?
אני רוצה לוודא פשוט כי נתקלתי כבר בגרסאות סותרות בין מה שלמדנו בשיעור
לבין מה שכתוב בספר של אורורה ברק:
באחד מסיכומי השיעור (של ארזים) כתוב שמספיק כל שבר גדול מאפס:
http://www.arazim-project.com/getfile.php?filename=public/complex10lec6.pdf
לעומת זאת, בספר של אורורה ברק, בע"מ 132 בספר האמיתי (לא גרסת האינטרנט.
אולי גם שם כתוב, לא יודע) כתוב שאיקס חייב להיות לפחות חצי.
אז מה הדרישה הנכונה?
תודה
Ido Ben Eliezer
Tom
משום מה לא מצאתי הגדרה כזאת בספר של אורורה ברק. הם מציינים ש
x
יכול להיות שווה לחצי, אבל הם לא אומרים שהוא יכול להיות יותר קטן.
On Jul 21, 11:10 am, Ido Ben Eliezer <idob...@gmail.com> wrote:
> בצורה שניסחת את זה x יכול להיות כל דבר, ועדיין זה יהיה שקול ל- BPP -- כלומר,
> כל עוד הפער בין קבלה דוחיה הוא לפחות 1 חלקי פולינום, הרי שבעזרת חזרה על הרצת
> המכונה מספר פולינומי של פעמים נקבל הסתברויות קבלה ודחיה של 1/3 ו- 2/3
> בהתאמה, ולכן זה יהיה שקול ל- BPP.
>
> 2010/7/21 Tom <tomtema...@gmail.com>
>
> אני מנסה לברר באופן סופי - האם הערך של ביתא במ"ט מסוג
> BPP
> חייב להיות גדול מחצי, או שכל שבר גדול מאפס ושגם גדול מאלפא בשבר שהוא
> לפחות פולינומי מספיק?
> כלומר, אם
> beta = x + 1/poly(n)
> alpha = x
>
> מה הגודל המינמלי של
> x
> ?
>
> אני רוצה לוודא פשוט כי נתקלתי כבר בגרסאות סותרות בין מה שלמדנו בשיעור
> לבין מה שכתוב בספר של אורורה ברק:
>
> באחד מסיכומי השיעור (של ארזים) כתוב שמספיק כל שבר גדול מאפס:
>
> http://www.arazim-project.com/getfile.php?filename=public/complex10le...