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

מתוך ויקיפדיה, האנציקלופדיה החופשית

ערך זה הוצע בעבר כמועמד להכללה ברשימת הערכים המומלצים לדיון ההמלצה

[עריכה] הערות

1. המשפט הראשון - אולי עדיף "בתורת הסיבוכיות, מערכת הוכחה אינטראקטיבית היא דיאלוג בין שתי קבוצות משתתפים שבמהלכו משכנעת קבוצת ה"מוכיחים" את קבוצת ה"מוודאים" בנכונותה של טענה חישובית מסויימת". "ייצוג מופשט של חישוב בתור דיאלוג"? אפשר בהמשך לומר שמערכות הוכחה משמשות לייצוג מופשט של חישובים.
2. "כמות המוכיחים" - "מספר המוכיחים".
3. בפסקה "NP כמערכת הוכחה" חסר ש- SAT היא NP complete.
4. "מתברר כי כוחה של מערכת ההוכחה הזו הוא גדול יחסית: ... IP זהה למחלקה PSPACE ... מחלקה גדולה יחסית": show, don't tell (בעיה שנמצאת ב-PSPACE ולא ב- ...).
5. Co-NP היא לא בדיוק "המחלקה המשלימה ל- NP" (ואם זו טרמינולוגיה מקובלת, אז היא מאד מבלבלת). עוזי ו. 11:41, 7 בנובמבר 2006 (IST)

תשובות:

1. יתוקן.
2. יתוקן. אתה האדם השני שאני שומע ממנו את התיקון הזה (בהקשרים שונים) בשבוע האחרון...
3. חסר, אבל אני לא חושב שרלוונטי כאן. SAT מובאת בתור דוגמה, ואיני בטוח שצריך להעמיס על הקורא בעוד מושג.
4. לא ברור מה אני אמור להראות, ואיך. ראשית, אולי PSPACE=P, אז להראות שפה שבודאות לא נמצאת ב-P אבל שייכת ל-PSPACE אי אפשר להראות (אלא אם אתה יכול, ואז אני חושב שיש לך מאמר לכתוב...). אפשר להראות את TQBF, שהיא PSPACE-שלמה, אבל לא ברור לי מה זה יגיד לקורא שלא כתוב כבר כעת. מה שכן ידוע הוא ש-PSPACE גדולה ממש מ-L (השפות שניתן לקבל ע"י מכונה דטרמיניסטית בזכרון לוגריתמי) וזה באמצעות משפט ההיררכייה לזיכרון - אבל זה די מסרבל לכתוב זאת כאן. לדעתי כדאי להשאיר את ה"להראות" לערך שעוסק ב-PSPACE.
5. אוי ואבוי. לא ברור לי מה לקחתי לפני שכתבתי את זה. יתוקן.

תודה רבה! גדי אלכסנדרוביץ' 13:51, 7 בנובמבר 2006 (IST)

[עריכה] הערה

בעקבות הפניה בדף ביקורת העמיתים- אני חסר ידע בנושא, וגם קריאה נוספת של פיסקת הפתיחה עדיין לא גורמת לי להבינה עד תומה. תוספת של הסבר אינטואטיווי יותר יכולה בהחלט להועיל, אני מאמין. שמעון נעים 21:42, 14 בדצמבר 2006 (IST)

תודה, אני אשמח לנסות ולשפר, אבל זה לא נושא שקל להציג אותו אינטואיטיבית. תוכל לנסות ולהצביע על נקודות שאתה מתקשה להבין? משפטים ספציפיים שאתה קורא ולא ברור לך מה רוצים ממך? הערות נקודתיות כאלו יכולות להיות מועילות מאוד. גדי אלכסנדרוביץ' 21:46, 14 בדצמבר 2006 (IST)