שיחה:P=NP

מתוך ויקיפדיה, האנציקלופדיה החופשית

[עריכה] שם הערך

לדעתי, שם הערך עלול לרמוז במידת-מה על נטייה למענה על השאלה. במרבית השפות שם הערך לא כולל את הסימן "=" או "≠" ובכך לא תופס, אפילו לכאורה, עמדה בנושא. אני מציע לשנות את שם הערך למשהו כמו "מחלקות הסיבוכיות P ו-NP", כמו שנעשה בגרסה האנגלית ובצורה זו או אחרת כמעט בכל שאר השפות שבהן מופיע ערך זה, ולהפנות אליו מ-"P=NP" ו-"P≠NP". Daniel1 00:55, 7 מאי 2006 (IDT)

"P=NP" הוא שמה הנפוץ של השאלה האם שתי המחלקות שוות. פסקת הפתיחה אינה משאירה מקום לספק שמדובר בבעיה פתוחה, ולא צריך לחשוש מ"תפיסת עמדה בנושא" יתר על המידה. עוזי ו. 01:11, 7 מאי 2006 (IDT)

שים לב, שאם מנסים לחפש את "P≠NP", לא מקבלים אף תוצאה. לעומת זאת אם מחפשים "P=NP", מגיעים לערך הנידון. בנוסף, אם כך נהגו ברוב הגרסאות של הערך הזה בוויקיפדיה, מה מצדיק את עצם היות הגרסה העברית יוצאת דופן? Daniel1 01:47, 7 מאי 2006 (IDT)

אין בעיה, אפשר להוסיף הפניה מ-"P≠NP" לכאן. כמובן, אתה מיתמם שלא לצורך - את P=NP קל לחפש, אבל את P≠NP לא ברור לי איך אפשר לחפש בלי להתחיל להסתבך עם כתיבת קודי ASCII. גדי אלכסנדרוביץ' 13:42, 7 מאי 2006 (IDT)

אפשר להוסיף סימן שאלה בסוף שם הערך, או לשנות את שמו ל"בעיית P=NP", אך אלה צעדים שרק יסבכו את שם הערך, וגם לפשטות יש חשיבות. דרך אגב, המשפט האחרון של פרמה איננו המשפט האחרון של פרמה, ועד לפני 12 שנה גם לא היה המשפט האחרון של פרמה, כך שאין להגזים בעניין זה. דוד שי 07:19, 7 מאי 2006 (IDT)

עד כמה שינוי שם המאמר ל"בעיית P=NP" יסבך את שם הערך? זה רק יהיה יותר מדויק וכמובן שאפשר לעשות הפניות לשם מ-P=NP בלי בעיה. Daniel1 14:07, 7 מאי 2006 (IDT)

אם "בעיית P=NP" היה שם מקובל יותר מאשר "P=NP", הייתי מסכים לשינוי. בינתיים יצרתי קישור משם לכאן. עוזי ו. 16:07, 7 מאי 2006 (IDT)

אנציקלופדיה היא לא אוסף של דברים שנחשבים ל"מקובלים" או "פופולאריים", אבל אני מבין שאין טעם להילחם כאן בטחנות רוח. אם זהו המצב, ניתן להפנות לכאן גם את "P≠NP", לא? Daniel1 20:07, 7 מאי 2006 (IDT)

לא, אבל שמות של מאמרים, אין סיבה שלא יהיו השמות הרווחים יותר בציבור (הערך שעוסק צ'ארלס לוטווידג' דודג'סון נקרא לואיס קרול). נראה לי שהדימוי העצמי שלך לדון קישוט מיותר. בכל מקרה, ההפנייה מP≠NP נוצרה. גדי אלכסנדרוביץ' 20:24, 7 מאי 2006 (IDT)

ממש לא התכוונתי לדמות את עצמי לדון קישוט, אלא להיפך. בכל מקרה, תודה! Daniel1 13:31, 8 מאי 2006 (IDT)

זכור לי שקראתי איפה שהוא (לא במילים אלו) שהשם "המשפט האחרון של פרמה" הוא בעצם קיצור של "המשפט האחרון שטרם הוכח או הופרך של פרמה", כך שיש הגיון כלשהו בשם (ובימינו הוא עדיין תקף למעט ה"טרם" וה"הופרך"). גדי אלכסנדרוביץ' 13:42, 7 מאי 2006 (IDT)

[עריכה] מצאתי! P שונה מ - NP!

הוכחה: לפי הערך, מוגדרות הקבוצות באופן הבא:

בתור P (מלשון Polynomial) מסמנים את אוסף בעיות ההכרעה שעבורן ידועים אלגוריתמים המוצאים פתרון בזמן ריצה פולינומיאלי.

בתור NP (מלשון Nondeterministic Polynomial) מסמנים את בעיות ההכרעה שעבורן ידועים אלגוריתמים הבודקים בזמן ריצה פולינומיאלי האם פתרון מוצע לבעיה אכן פותר אותה. אלגוריתמים אלו לא בהכרח מסוגלים למצוא פתרון, אלא רק לוודא שפתרון מוצע הוא אכן נכון.

ובכן, ניקח בעיה הנמצאת ב - NP complete (למשל "האם מסילה היא מסילה המילטונית בגרף"). עבור בעיה זאת, ידוע אלגוריתם פולינומיאלי הבודק אם מסילה מוצעת היא אכן המילטונית (כלומר הבעיה ב - NP) אבל לא ידוע אלגוריתם פולינומיאלי המוצא מסילה המילטונית (כלומר היא לא ב - P). מכאן שהקבוצות P ו NP שונות.

מוקדש באהבה לדוד שי הטוען בלהט ליעילות הביקורת שלאחר הפירסום. אגב, המילה ידועים(במקום קיימים) מופיעה בערך כמעט שנה (ונכתבה ע"י אחד הכותבים המחוננים ביותר בוויקיפדיה).יבחוש 23:31, 28 בדצמבר 2006 (IST)

אכן, שגיאה מביכה למדי, ותמוה בעיני שאף אחד (ובפרט אני) לא עלה עליה עד כה. גדי אלכסנדרוביץ' 23:33, 28 בדצמבר 2006 (IST)

הקינטור היה מופנה בעיקר לדוד..אגב, אני מלא הערכה על האופן הפשוט והבהיר בו מוצג נושא חמקמק זה. ועוד הצעה זוטא: אולי עדיף במקום "שקיימים אלגוריתמים המוצאים...", לכתוב "שקיים אלגוריתם המוצא.." ..מספיק אחד, לא צריך להגביל את הכלליות.. (אבל אולי מדובר כבר בדקדוקי עניות).יבחוש 23:46, 28 בדצמבר 2006 (IST)

זה קצת בעייתי כי עלולים לקבל את הרושם שמדובר על אלגוריתם אחד שפותר את כל הבעיות ב-P, וגו'. כמובן שאפשר להתחכם ולומר שקיים אלגוריתם כזה כי יש רק מספר בן מניה של בעיות ב-P... גדי אלכסנדרוביץ' 00:09, 29 בדצמבר 2006 (IST)

כידוע, אינני טוען ליעילות מוחלטת של בקרה לאחר פרסום, ואני מקווה שאיש אינו טוען ליעילות מוחלטת של בקרה לפני פרסום. כל שאני טוען הוא שהבקרה שלאחר פרסום בוויקיפדיה מניבה תוצאה שאיכותה אינה נופלת מזו שמופקת בסביבות אחרות באמצעות בקרה לפני פרסום. כדי לקנטר אותי, יש לסתור טענה זו, וזו כמובן משימה הרבה יותר קשה. טעות בודדת שנמצאה אינה אומרת דבר, ראה ויקיפדיה:אמינות לשלל טעויות שנמצאו במקורות עם בקרה קפדנית לפני פרסום. דוד שי 00:11, 29 בדצמבר 2006 (IST)

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

גדי, אכן בעיית ניסוח קשה. ניסיתי לחשוב על כמה ניסוחים ופסלתי אותם. האם אתה מרוצה מהמצב הקיים? גם הוא לא לחלוטין מדוייק. הדרישה לקיום מספר אלגוריתמים מקטינה את הקבוצה.יבחוש 00:54, 29 בדצמבר 2006 (IST)

הי, תראו מה מצאתי ..אולי אפשר להנות משני העולמות.יבחוש 01:08, 29 בדצמבר 2006 (IST)

גדי, נראה לי שהשינוי האחרון שעשית פותר את הבעיה. זה שמדובר בהכלה ולא בשוויון אינו משמעותי לדעתי (אפשר היה להוסיף "ורק הם" אבל זה באמת כבר היה מסורבל). נראה לי שב - trade off בין ניסוח פשוט ואינטואיטיבי לבין דיוק מתמטי, המצב בסדר. אגב, לפי מה שקלטתי כבר ("כלה זמנך בכתיבת ערכים במקום לבלותם בדפי שיחה") בתרבות הויקי של ארץ הקודש, כל מה שכתבתי כאן נחשב כהצקה בלבד. נו שו‏ֹ‏‏יין, לפחות בחרתי לי שם משתמש מתאים - יבחוש 08:23, 29 בדצמבר 2006 (IST)

אין לי מושג מה קלטת, אבל אין שום הצקה בהערות שלך. ביקורת על תוכן ערכים בדף השיחה חשובה לפחות כמו כתיבתם. גדי אלכסנדרוביץ' 10:58, 29 בדצמבר 2006 (IST)

הלינק שהבאתי בדברי האחרונים וכל הדיבורים במזנון על סטטיסטיקות ויחס בין תרומות במרחבים השונים. קלטתי משהו לא קיים או רק משהו שהוא בניגוד לדעתך?יבחוש 14:25, 29 בדצמבר 2006 (IST)

בוודאי שהוא קיים, וחבל שכך. לי אישית העיסוק האווילי בסטטיסטיקות יצא מהחורים כבר מזמן. בנוסף, בהקשר של דברייך: הבעיה היא שלא מפרידים בין אנשים שבאים ומקשקשים כל היום על איך צריך לנהל את ויקיפדיה, ובין אנשים שבאים וכותבים בדפי שיחה הערות של טעם לגופם של הערכים. הסטטיסטיקות עיוורות לזה לגמרי. גדי אלכסנדרוביץ' 14:35, 29 בדצמבר 2006 (IST)

ושיחות לגבי איך צריך לנהל את ויקפדיה, אינן חשובות לדעתך?יבחוש 15:00, 29 בדצמבר 2006 (IST)

לטעמי רובן המכריע עקרות, ואם הן מובילות להחלטה כלשהי, אותה החלטה מתגלה לרוב בתור בכיה לדורות (כמו "כללי ההתנהגות בין חברי הקהילה"). לכן צריך לנהוג בהן בתור רע הכרחי בלבד. מי שכל תרומתו לויקיפדיה מתמצה בהשתתפות בדיונים הללו, אחד משניים: או שהוא נמצא כרגע בתקופת משבר כתיבה וזה יעבור לו (ואפשר וראוי לדרבן אותו לכתוב ערכים על ידי הצבעה על דברים שמעניין לכתוב עליהם/לערוך אותם) או שלא כדאי לו להישאר כאן וכדאי לו לחזור עוד כמה חודשים אחרי שיעבור לו. גדי אלכסנדרוביץ' 15:32, 29 בדצמבר 2006 (IST)

אמשיך את שיחתי המקבילה עם יבחוש בעניין בקרת פרסום: "קל לראות שעבור אותה ביקורת, ביקורת לפני פרסום עדיפה על ביקורת אחרי פרסום", כותב יבחוש. כאשר בערך מתמטי נכתבות המילים קל לראות, יש להזכיר את הסיפור הנודע על הארדי בהקשר זה. כמו במקרה של הארדי, גם כאן לא כל כך קל לראות. למשל: ביקורת לפני פרסום, שנעשית על-ידי מעט מבקרים עמוסי עבודה, נמשכת זמן רב (לעתים אפילו שנה), ומעכבת את הפרסום. אותה ביקורת, לאחר פרסום, ניתנת להיעשות על-ידי רבים, ולהסתיים הרבה יותר מהר. כיוון שאנו ממילא בערך מתמטי, ראוי להזכיר את החלטתו של גריגורי פרלמן לפרסם את הוכחתו להשערת פואנקרה ללא בקרה לפני פרסום. ביקורת לפני פרסום הייתה חיונית בעידן הדפוס, אבל עידן האינטרנט מחייב אותנו לחשיבה מחודשת בעניין זה, אחרת נראה כבן המאה ה-19 המצטייד בשוט לפני כניסתו למכונית, כפי שנהג קודם לכן בעת שרכב על סוס. נדמה לי שהגיע הזמן לעסוק בהשוואה יסודית יותר של שתי שיטות אלה להוצאה לאור, על יתרונותיהן וחסרונותיהן. דוד שי 15:24, 29 בדצמבר 2006 (IST)

אתה צודק. באמת זה מזמין דיון מסודר. אנסה למצוא זמן לנסח את מחשבותי בעניין ולכתוב אותם במרחב המשתמש שלי. הבעיה שכרגע יותר בוער לי לטפל באיכות הסביבה. נושא חשוב שלדעתי דורש טיפול.יבחוש 16:11, 29 בדצמבר 2006 (IST)

ולגדי - קראתי לאחרונה הרבה בארכיוני המזנון. קראתי משהו שאורי מוסינזון כתב על נורמות התנהגות כתחליף לחוקים ועל העובדה שהנורמות האלה מתעצבות כל הזמן תוך כדי השיחות והויכוחים. אני חושב שזה נכון. לדעתי הנורמות של ויקיפדיה העברית הן בעיתיות (לעומת אלה של האנגלית) אבל אתה דוקא מייצג את הצד שיותר קרוב לנורמות הנהוגות שם.יבחוש 16:17, 29 בדצמבר 2006 (IST)