קצת נתקעתי בהוכחה בכיוון שבו יש לנו שפה ששייכת ל-

NP

וצריך לבנות מוודא.

הנחנו כי דרגת הפיצול בעץ הינה 'בי'. כמו כן אמרנו שכל מסלול הוא פולינומיאלי באורכו, כתבנו רצפי אותיות מעל 1-בי כדי לחקות מסלול חישוב - ואז אמרנו שבנינו מחרוזת שהיא מאורך לכל היותר 'אן בחזקת בי'. למה זה האורך?

a language is in MP if and only if it has a polynomial time verifier