אלגוריתם פולינומיאלי לClique?

[gil levi]

אלגוריתם פולינומיאלי לClique?

היי, במהלך פתרון תרגיל בסיבוכיות, אני חושב שמצאתי אלגוריתם פולינומיאלי לבעיית Clique, או יותר נכון- לוואריאציה שלה: קלט: גרף G ומספר טבעי K. שאלה: האם קיים בG קליק בגודל בדיוק K? האלגוריתם שלי הוא הבא: נמצא את כל הקודקודים בגרף שדרגתם בדיוק K-1 (בזמן לכל היותר n^2 כאשר n הוא מספר הקודקודים), נניח שיש t כאלו. עבור כל אחד מהם, נבדוק האם K-1 שכניו גם הם מדרגה K-1. אם כן, אז קיים קליק בגודל בדיוק K. אחרת, לא קיים כזה. איפה הטעות בפתרון שלי? תודה, גיל.

 

[W12X]

סתירה

קח ארבעה קוקודים ותחבר אותם כמעגל , כל אחד מהם דרגתו 2 , אם תחפש 3-קליק לפי האלגורתים שהצעת אז הוא יחזיר שיש 3-קליק בעוד זה לא נכון לילה טוב

 

[gil levi]

ועוד משהו לא ברור:

נניח שנתונה בעיית SUBSET-SUM כאשר המספרים הניתנים כקלט הם בייצוג אונרי, כלומר הבעיה הבאה: קלט: רשימה של מספרים טבעיים A1,..,An ומספר T. כל המספרים ניתנים בייצוג אונרי, כלומר המספר K מיוצג כ 1 בחזקת K. שאלה: האם קיימת תת קבוצה של A1,...,An שסכומה T? יש לבעיה פתרון בזמן O(n*T)zzz. מדוע באופן כללי זה אינו פתרון פולינומיאלי בגודל הקלט, אבל במקרה הזה הוא כן פולינומיאלי באורך הקלט? תודה רבה, גיל.

 

[W12X]

אתה מתכוון למקרה ספציפי ?

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

 

[gil levi]

לא כל כך הבנתי..

מדוע פתרון בזמן של O(n*T) zzz אינו פולינומיאלי באורך הקלט במקרה הכללי, אבל במקרה הפרטי שבו המספרים נתונים בייצוג אונרי הוא כן פולינומיאלי? תודה, גיל.

 

[W12X]

אה , מאוד פשוט

אם המספר i נתון בייצוג אונרי , אזי o זה בעצם גם o(i) tאבל אם הוא נתון בייצוג אחר ( למשל - עשרוני) אזי זה לוקח 10 בחזקת n ולכן זה לא פוליניאלי.....

 

[W12X]

ובמלים פשוטות

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

 

[gil levi]

תודה רבה!

 

[carlos22]

אתה מבלבל בין שני מושגים

אורך וגודל זמן הריצה נמדד בסדרי גודל של אורך הקלט ואם מספר מיוצג בבסיס אונארי אז האורך שלו הוא הגודל שלו ואם מספר מיוצג בבסיס אחר אז האורך שלו הוא לוגוריתמי ביחס לגודל.

 

[gil levi]

תודה רבה!