שיחה:בעיה NP-שלמה

שם הערך

לדעתי שם יותר טוב לערך יהיה "NP-שלמות", או "בעיה NP-שלמה" או "NPC" או "מחלקת הסיבוכיות NPC". 14:03, 6 מרץ 2006 (UTC)

בהמשך אני אחשוב על השאלה הזאת. בינתיים, היא נשארת עם השם שניתן לה ע"י המחבר המקורי (משתמש אנונימי).

הערות על הערך

1. שם הערך עדיין בעייתי. לדעתי עדיף "מחלקת *ה*סיבוכיות NPC" (בלי ההדגשה). צריך גם לשנות את הפתיחה ה"הגדרתית" בהתאם לנושא הערך.
2. הפתיחה היא בעיה (NP) קשה. אנו משליכים על הקורא שלושה מושגים לא ברורים: "בעיית הכרעה", "רדוקציה פולינומיאלית" ו"המחלקה NP" כשהעצם שאנחנו זורקים לו בסוגריים כדי לשפר את ההבנה שלו הוא עוד מושג שאם הוא ידוע למישהו, הוא ממילא לא צריך את ההקדמה: "NP-קשה". ה"כלומר" שמגיע אחרי הסוגריים הוא חסר משמעות - ההגדרה של בעיה NP קשה היא ככזו שיש אליה רדוקציה מכל בעיה ב-NP, ולכן אין כאן "כלומר", וממילא החלק הזה לא מדבר בכלל על NPC.
3. איפה שהוא בהקדמה התפספס הרעיון הבסיסי של המחלקה: שהיא מכילה את הבעיות ה"קשות ביותר" מבין אלו שהן NP, ובגישה אחרת: הבעיות ה"קסומות" שבעזרת פתרון יעיל עבורן אפשר לפתור כל בעיה אחרת ב-NP בצורה יעילה. אפשר לומר את זה בלי להיכנס למושגים טכניים. בערך הנוכחי מגיעים לזה רק בשורה הרביעית, אחרי שכבר "הרגנו" את הקורא שאינו בקיא במושגים.
4. כשמדברים על ביצוע רדוקציה כדאי לזכור שהדבר הכי חשוב הוא שהפלט של בעיה ב' הוא גם הפלט שבעיה א' אמורה להוציא.
5. "רדוקציה פולינומיאלית" עושה לי כואב בעיניים. עדיף לכתוב "פולינומיאלית" רק בהתחלה ומאז לכתוב רק רדוקציה בצורה שתבהיר שהיא תמיד פולינומיאלית. יש לשים לב שגם בערך הנוכחי לפעמים כותבים רק "רדוקציה" כשהכוונה היא לרדוקציה פולינומיאלית.
6. זה נחמד שהשאלה היא אחת משאלות מיליון הדולר, אבל מהן שאלות מיליון הדולר?
7. מה מפתיע בכך שבעיות NP שלמות קיימות? זה מגניב, לא מפתיע.
8. למה חשוב לציין שמשפט קוק-לוין הוכח עצמאית בידי לוין? צריך גם לציין, אם כך, שקוק הוכיח אותו עצמאית גם כן.
9. בכלל, די צורמת הכפילות של הדיבור על SAT ומשפט קוק-לוין בשני מקומות שונים, ובשתי צורות שונות ("בעיית הספיקות...").
10. בעית התכנון הלינארי בשלמים של קארפ היא של 0-1 (כלומר, הערכים שהמשתנים יכולים לקבל הם רק 0 או 1).
11. ב-3SAT, למה להשתמש ב"קלוז" כשאפשר "פסוקית"?
12. יש כמה וכמה הגהות לבצע ("שמן פולינומי") וגם צריך להחליט אם אנחנו בעד "פולינומי" או "פולינומיאלי".
13. הנושא המרתק של קירובים לפתרונות של בעיות NP שלמות ראוי להרבה יותר מאשר אזכור בן שורה אחת בסוף הערך.

זהו לבינתיים. גדי אלכסנדרוביץ' 23:15, 27 מרץ 2006 (UTC)

רשימת ה-21

מהי ההיררכיה המשתמעת מן ההסחות? עוזי ו. - שיחה 22:31, 22 ביולי 2008 (IDT)

שם הערך 2

לדעתי שם הערך צריך להיות "בעיה NP-שלמה". השם הזה הרבה יותר הגיוני ומובן לדוברי עברית ומסביר קצת יותר טוב את מהות הערך מאשר ראשי התיבות האנגליים "NPC". בברכה, דניאל • שיחה 00:00, 27 באוקטובר 2008 (IST)

האם "בעיית NP שלמה" יכול להיות שם ברור יותר? אלדד • שיחה 00:58, 27 באוקטובר 2008 (IST)

לדעתי כן, כי ה־C ב־NPC מקצרת את המילה Complete, לכן פשוט מדובר ב"פתיחה" של ראשי התיבות והפיכת המושג למושג קצת יותר עברי... דניאל • שיחה 07:14, 27 באוקטובר 2008 (IST)

אני בעד. דוד שי - שיחה 07:56, 27 באוקטובר 2008 (IST)

גם אני בעד. יובל מדר - שיחה 00:18, 28 באוקטובר 2008 (IST)

בעיית NP שלמה? בשביל מה הסמיכות? (הבעיה של NP שלמה? מה זה אומר?) השם הנכון לדעתי הוא השם שהציע דניאל (בעיה NP-שלמה, עם או בלי המקף) יובל מדר - שיחה 00:21, 28 באוקטובר 2008 (IST)

כן, כשכתבתי "אני בעד" התכוונתי להצעה המקורית של דניאל. דוד שי - שיחה 06:53, 28 באוקטובר 2008 (IST)