פורטל:מדעי המחשב/מאמר נבחר/11

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

כל מערכות ההוכחה האינטראקטיביות נדרשות לקיים שתי תכונות בסיסיות:

• שלמוּת: אם טענה כלשהי נכונה, ואם הן המוכיח והן המוודא פועלים על פי הפרוטוקול, המוכיח יצליח לשכנע את המוודא בנכונות הטענה.
• נאותוּת: אם טענה כלשהי אינה נכונה, אף מוכיח - גם כזה שהוא "רמאי" ואינו פועל על פי הפרוטוקול - לא יצליח לשכנע את המוודא בנכונות הטענה, אלא בהסתברות נמוכה.

לערך המלא