שאלה לגבי הגדרות
שפה L שייכת ל-NP אם קיים אלגוריתם פולינומי V ופלינום p כך ש:
zz x in L <=> there is y in {0,1}^(p(|x|)) such that V(x,y) = 1 zz (*)
מגדירים את co-NP כך: zz co-NP = {L | L' in NP} zz כאשר 'L, הכוונה ל-L משלים.
תרגיל:
הראה ששפה L שייכת ל-co-NP אם קיים אלגוריתם פולינומי V ופולינום p כך ש:
zz x in L <=> for each y in {0,1}^(p(|x|)) , V(x,y) = 1 zz
משהו לא ברור לי..x שייך לשפה L ששייכת ל-co-NP, אם מתקיימת שלילת הטענה שנמצאת מימין לסימן <=> שבשורה שמסומנת ב-(*), לא?
אם כן, אז במקום V(x,y)=1 צריך להיות V(x,y)=0..?
אשמח להבין איפה הטעות שלי, ואיך מראים את מה שמבקשים.
תודה מראש
שפה L שייכת ל-NP אם קיים אלגוריתם פולינומי V ופלינום p כך ש:
zz x in L <=> there is y in {0,1}^(p(|x|)) such that V(x,y) = 1 zz (*)
מגדירים את co-NP כך: zz co-NP = {L | L' in NP} zz כאשר 'L, הכוונה ל-L משלים.
תרגיל:
הראה ששפה L שייכת ל-co-NP אם קיים אלגוריתם פולינומי V ופולינום p כך ש:
zz x in L <=> for each y in {0,1}^(p(|x|)) , V(x,y) = 1 zz
משהו לא ברור לי..x שייך לשפה L ששייכת ל-co-NP, אם מתקיימת שלילת הטענה שנמצאת מימין לסימן <=> שבשורה שמסומנת ב-(*), לא?
אם כן, אז במקום V(x,y)=1 צריך להיות V(x,y)=0..?
אשמח להבין איפה הטעות שלי, ואיך מראים את מה שמבקשים.
תודה מראש