חישוב לא דטרמינסטי

נגדיר אלגוריתם לא דטרמינסטי כאלגוריתם שבכל צעד יתכנו כמה אפשרויות

הגדרה
נאמר כי אלג׳ ל״ד $A$ מכריע בעיה $S$ אם מתקיים:

• $x\in S$ $\leftarrow$ קיימת ריצה עבורה $A(x)=1$
• $x\notin S$ $\leftarrow$ בכל ריצה $A(x)=0$

הגדרה שקולה למחלקה NP

אם כן, נוכל להגדיר את המחלקה $NP$ על ידי

טענה: 2 ההגדרות של NP הן שקולות
הוכחה:
תהי בעיה $S\in NP$ לפי ההגדרה המקורית, כלומר קיים פולינום $P$ ומוודא פולינומי $V$ כך ש $x\in S\leftrightarrow {\mathrm{\exists }}_{y:|y|\le P(|x|)}:V(x,y)=1$ . נגדיר אלגוריתם ל״ד $A$ המכריע את $S$:

A(x):
	y = ""
	while y <= P(|x|) choose in a indetermistic way between:
		1) y = y+0
		2) y = y+1
		3) break
	return V(x,y)

נשים לב ששלב הבחירה נעשה לכל היותר $P(|x|)$ פעמים ו $V$ אלג׳ פולינומי לכן $A$ פולינומי.
כמו כן:
$x\in S$ אמ״מ קיים $y$ באורך לכל היותר $P(|x|)$ כך ש $V(x,y)=1$ אמ״מ קיימת בחירה של $y$ כך ש $A(x)=1=V(x,y)$ בשורה האחרונה של הקוד. לכן $S\in NP$ גם לפי ההגדרה השקולה.

בכיוון השני, נניח $S\in NP$ לפי ההגדרה השקולה.
כלומר קיים אלגוריתם פולינומי $A$ שמכריע את $S$. נסמן ב $P$ את הפולינום שחוסם את זמן הריצה של $A$ ונגדיר אלגוריתם דטרמינסטי $V$ שמקבל $(x,y)$ ופשוט מריץ את $A(x)$ . השימוש ב $y$ יהיה כדי לקבוע את הבחירות הל״ד של $A$ כלומר, לפי הביט ה $i$ מתבצעת הבחירה ה$i$ באלגוריתם הל״ד.
כמובן ש $V$ פולינומי ובנוסף :
$x\in S$ אמ״מ קיימת ריצה עבורה $A(x)=1$ אמ״מ קיים $y$ חסום ב $P(|x|)$ כך ש $V(x,y)=1$ ולכן $S\in NP$ לפי ההגדרה המקורית.