הוכחה אינטראקטיבית היא דיאלוג בין שתי קבוצות משתתפים. הקבוצה הראשונה היא המוכיחים (מי שמנסה לשכנע). השנייה היא המוודאים (מי שבודק). השיחה מתנהלת לפי כללי תקשורת שנקראים פרוטוקול.
במערכת כזו נדרשות בדרך כלל שתי תכונות בסיסיות: שלמות (אם הטענה נכונה, המוודא יתקבל) ונאותות/ soundness (אם הטענה שקרית, רמאי לא יצליח לשכנע את המוודא, או שיעשה זאת רק בהסתברות נמוכה).
ההגדרה הראשונה של הוכחה אינטראקטיבית ניתנה באמצע שנות ה-80 על ידי צוות שכלל את לסלו בבאי, שפי גולדווסר, סילביו מיקאלי, שלמה מורן וצ'ארלס ראקוף. צוות זה קיבל את פרס גדל ב-1993 על העבודה הזו.
דוגמה ידועה היא הפסנתרן דניאל בארנבוים. המראיין מבקש ממנו לנגן יצירה אקראית של מוצרט. בארנבוים מנגן, והמראיין משכנע עצמו שהוא יודע את היצירות בעל-פה. כאן המוכיח הוא בארנבוים, והמוודא הוא המראיין. הפרוטוקול מבוסס על בחירת יצירות אקראית על ידי המוודא. אם השאלות היו ניתנות מראש, רמאי היה יכול להתכונן ולרמות, לכן אי־ידיעת השאלות מראש חשובה (נאותות).
ממשקי הוכחה שונים נבדלים בכמות המוכיחים ובכמה חזק המחשב של המוודא והמוכיח. לדוגמה, ב-NP הפרוטוקול פשוט: המוכיח שולח אישור (witness), והמוודא הדטרמיניסטי בודק אותו בזמן פולינומי. כאן האינטראקטיביות פחותה, כי המוכיח רק שולח הוכחה אחת.
אם מרשים למוודא להשתמש בהטלות מטבע אקראיות ולנהל החלפת הודעות פולינומית פעמים, מקבלים את המחלקה IP. במערכת זו המוודא הוא מכונת טיורינג הסתברותית בריצה פולינומית. אפשר להרשות לו לטעות בהסתברות קטנה. עדי שמיר הוכיח ב-1990 כי IP שווה ל-PSPACE, כלומר כוחה של מערכת הוכחה הסתברותית אינטראקטיבית גדול למדי.
בבעיית איזומורפיזם הגרפים בודקים אם שני גרפים זהים אחרי שינוי שמות הצמתים. הפרוטוקול הסטנדרטי עובד כך: המוודא בוחר אחד מהגרפים באקראי, מיישם עליו תמורה (החלפת שמות) ושולח למוכיח. המוכיח צריך לזהות איזה גרף נבחר. אם הגרפים שונים אפשר לזהות זאת בביטחון; אם הם זהים, המוכיח יכול רק לנחש, וההסתברות שיזכה יורדת עם חזרות הפרוטוקול.
הוכחה באפס ידע היא פרוטוקול שבו המוודא לא לומד שום מידע חדש מעבר לעובדה שהטענה נכונה. זה חשוב בקריפטוגרפיה ובמערכות זיהוי. את אפס הידע מפרמלים באמצעות רעיון ה'סימולטור', מכונה שמייצרת תעתיקים של השיחה בלי גישה לסוד. אם הסימולטור מסוגל לייצר את התעתיקים, המוודא לא קיבל מידע חדש.
הרחבה אחרת היא להוסיף מוכיחים שאינם מדברים זה עם זה. זו המחלקה MIP (מרובת מוכיחים). המוכיחים הנפרדים מקשים על רמאים להתאים תשובות, ולכן המערכת חזקה יותר. הוכח כי MIP שווה ל-NEXP.
פרוטוקול ארתור-מרלין דומה ל-IP, אך כל ההגרלות של המוודא גלויות גם למוכיח. אם מרשים מספר סיבובים פולינומי, הכוח נשאר IP.
מערכת PCP (Probabilistically Checkable Proof) מאפשרת למוודא לקרוא רק חלק קטן מההוכחה ולבצע הטלות מטבע. תוצאות מרכזיות מראות שדי בקריאת מעט סיביות ובמספר לוגריתמי של הטלות מטבע כדי לקבל שפות שב-NP. אירית דינור נתנה הוכחה חדשה של משפט ה-PCP ב-2005, וזכתה בפרס ארדש ב-2012.
הוכחה אינטראקטיבית היא שיחה בין מי שטוען משהו לבין מי שבודק. המוכיח מנסה לשכנע. המוודא בודק.
דניאל בארנבוים אמר שהוא למד לנגן את כל היצירות של מוצרט. כדי לבדוק, המראיין בחר יצירה אקראית. בארנבוים ניגן אותה. כך המראיין השתכנע. כאן המוודא בוחר שאלות לא מראש. זה עוזר לא לגלות רמאים.
פרוטוקול הוא חוקי השיחה בין המוכיח והמוודא. שלמות אומרת: אם הטענה נכונה, המוודא יאמין. נאותות אומרת: אם הטענה שקרית, רמאי לא ישכנע בקלות.
NP היא דוגמה פשוטה. המוכיח שולח 'אישור' קצר. המוודא בודק אותו מהר.
שתי תמונות של קשרים נקראות גרפים. כדי לבדוק אם הם זהים לאחר שינוי שמות, המוודא עושה שינוי אקראי ושואל את המוכיח איזה גרף זה. אם הם זהים, המוכיח צריך לנחש.
אפס ידע אומר שהמוודא לומד רק שהטענה נכונה. הוא לא לומד סודות נוספים. זו שיטה חשובה לאבטחה וזיהוי.
MIP משתמש ביותר ממוכיח אחד. זה מקשה על רמאים. PCP אומר שאפשר לבדוק חלק קטן מההוכחה ולהבין אם היא נכונה. אירית דינור נתנה הוכחה חשובה ב-2005 וזכתה בפרס ב-2012.
תגובות גולשים