לי באופן אישי אין זמן לקרוא כרגע את ההוכחה, ובאופן אישי זוהי אינה בעייה המעניינת אותי באופן משמעותי. עם זאת אין לשכוח כי מדובר בבעיית מילניום שפתרונה יזכה את הפותר במיליון דולר.

ההוכחה שהוגשה לבדיקה:
http://www.scribd.com/doc/35539144/pnp12pt

קצת מידע על הבעייה עצמה:
את הבעייה מגדירים בד"כ עם מכונת טיורינג.
(בקצרה מכונת טיורינג - יש כמה מודלים שקולים של הגדרת מכונת טיורינג. אנחנו נחשוב על מכונת טיורינג כמכונה עם 3 סרטים - סרט קלט, סרט עבודה וסרט פלט. יש לה א"ב של מכונה המכיל את הא"ב של שפה. נניח כי א"ב של השפה יהיה מעל {0,1}. יש לה שני ראשים - ראש שמצביע על מיקום בסרט הקלט וראש שמצביע על מיקום בסרט העבודה. במצב ההתחלתי ראש הקלט מצביע על התו הראשון במחרוזת וראש הפלט מצביע על המיקום הראשון בסרט העבודה. יש לה פונקצית מעברים - בהנתן תו מעל הא"ב (מסרט הקלט) ומצב, היא כותבת על המיקום הנוכחי בסרט העבודה תו כלשהו, עוברת שמאלה או ימינה (על סרט העבודה והקלט כרצונה) ועוברת מצב.).
P ו-NP הינן מחלקות של שפות כדלהלן:
P מייצגת את אוסף השפות שניתן לפתור בעזרת מ"ט דטרמינסטית (כמוגדר לעיל) בזמן פולינומיאלי באורך הקלט, לדוגמא חיפוש DFS, BFS, אלגוריתמי זרימה.
NP מייצגת את אוסף השפות שניתן לפתור בעזרת מ"ט אי-דטרמינסטית בזמן פולינומיאלי באורך הקלט, לדוגמא מציאת קליקה גדולה ביותר בגרף, האם נוסחא בצורת 3SAT/SAT היא ספיקה.
אי דטרמיניזם פירושו שהמכונה יכולה בהנתן מצב, לעבור למספר מסויים של מצבים, כך למשל במקום לרוץ במסלול אחד, אפשר לתאר את הריצה שלה ע"י עץ של מצבים והמכונה מקבלת אמ"ם קיים מסלול המסתיים במצב של קבלה. ברור איפוא כי P מוכל ב-NP אך השאלה היא האם מוכל ממש.

לבעייה יהיו השלכות רבות במידה ויוכח כי P = NP. במצב זה לא רק שזה יוכיח כי בעיות קשות ניתן לפתור בקלות אלא גם נוכל להסיק כיצד לפתור אותן (הוכיחו את זה). הדעה הרווחת היא ש-P != NP ורוב האנשים העוסקים בתחום סבורים כך.