[-] עד פולינומי
by davidkur - Tuesday, 26 June 2012 22:45:19
לפי מה שראינו בתרגול,
אם איקס בשפה אז
קיים עד החסום ע"י פולינום של הקלט איקס.
והאלג מחזיר אמת
אם איקס לא בשפה, אז לכל עד פולינומי, האלג' או המכונה מחזירים
false

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

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

אבל בפועל המכונה צריכה לעשות את זה...

אבל איך היא יודעת אם העד פולינומי בקלט או לא?

אם היא תתחיל לספור היא לא תסיים.

האם אפשר איכשהו בבקשה לחדד את הנקודה הזאת?
thread
Re: עד פולינומי
by beimel - Thursday, 28 June 2012 02:01:39
אלגוריתם הוידוא יודע מהו הפולינום שחוסם את אורך העד. לכן, בהינתן קלט ועד הוא יכול לוודא אם אורך העד לא חסום על ידי הפולינום הנ"ל ובמקרה זה לדחות

בד"כ שמתארים אלגוריתם אימות זה לא בעיה, לדוגמא עבור בעיית כיסוי בצמתים העד הוא תת קבוצה של צמתים ואם אלגוריתם האימות מקבל עד שאינו מתאר קבוצה אזי הוא דוחה
thread