בהרצאה הוצג אלגוריתם הסתברותי לבעיית וידוא כפל מטריצות. נציע להלן שני אלגוריתמים נוספים לבעיה זו. עבור איזה ער…

בהרצאה הוצג אלגוריתם הסתברותי לבעיית וידוא כפל מטריצות. נציע להלן שני אלגוריתמים נוספים לבעיה זו. עבור איזה ערך של $m$ שני האלגוריתמים מבטיחים את אותו חסם על הסתברות ההצלחה? הוכיחו את קביעתכם במלואה.

1. אלגוריתם אשר מריץ את האלגוריתם מההרצאה $10$ פעמים באופן בלתי תלוי, ומקבל אם ורק אם מתקבלת תשובה חיובית בכל אחת מ-$10$ ההרצות.
2. אלגוריתם אשר פועל כמו האלגוריתם מההרצאה עם השינוי שלהלן: הווקטור $r$ מוגרל מהתפלגות אחידה על $\{0,1,\ldots,m\}^n$ במקום על $\{0,1\}^n$.