שיחה:בעיית 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)

שינוי השם

שם הערך שונה ללא הסכמה בדף השיחה. החזרתי עד אשר תהיה הסכמה. בברכה, אבינעם - שיחה 16:04, 28 במאי 2008 (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)

הסבר לשחזור שלי

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

פ]ורמלית, המושג "זמן ריצה" כשלעצמו חסר משמעות, משום שמדובר בפונקציה של הקלט. כשהקורא התמים רואה את המילה "זמן" הוא חושב על יחידות זמן כמו דקות ושניות ואני לא בטוח שהמלים "צעד בסיסי" עוזרות לו להבין במה מדובר. בכלל אני חושב שהצגת הדברים קצת פחות מידי פורמלית. אני לא אוהב את המשפט "קלטים גדולים יותר לבעיה גוררים לרוב זמן פתרון גדול יותר". הכוונה היא שהבעיות המעניינות הן אלה שזמן הריצה תלוי באורך הקלט. אבל אני יכול לכתוב אלגוריתם שעוצר ללא תלות בזמן הריצה, ולמעשה אינסוף אלגוריתמים כאלה, אז מה הכוונה ב"לרוב"? הנס מאייר - שיחה 16:12, 14 בספטמבר 2009 (IDT)

ב"לרוב" הכוונה ל"לרוב, כשפותרים בעיות אמיתיות". פורמליזם זה אחלה, וזה בדיוק המקום שאליו הפסקה הולכת בסופו של דבר, אבל בהתחלה הוא לא הכרחי. גדי אלכסנדרוביץ' - שיחה 18:36, 15 בספטמבר 2009 (IDT)

ראיתי את התוספת שגדי הוסיף היום בערך. לדעתי כיום יש פתרון פולינומאלי לאלגוריתם הסימפלקס אלא שבישומים מעשיים הוא נותן תוצאות גרועות יותר מהשיטות האחרות. תומר א. - שיחה 23:21, 15 בספטמבר 2009 (IDT)

הכוונה לאלגוריתם הסימפלקס הבסיסי; אין הגיון בלהכביר פרטים לא רלוונטיים כאן (מי שמתעניין, שיכנס לערך המתאים לכשיכתב). גדי אלכסנדרוביץ' - שיחה 10:21, 16 בספטמבר 2009 (IDT)

בערך כתוב, למעשה, שאלגוריתם הסימפלקס נחשב לבעל זמן ריצה סביר על-אף שהוא אקספוננציאלי. זה מטעה, משום שזמן ריצה נמדד כידוע לפי המקרה הגרוע ביותר, ושם אכן אלגוריתם הסימפלקס חסר תועלת; הוא שימושי רק מפני ש*בדרך כלל*, זמן הריצה שלו *פולינומיאלי*. עוזי ו. - שיחה 11:01, 16 בספטמבר 2009 (IDT)

עוזי, זה לא מדויק. אמנם בד"כ מודדים לפי המקרה הגרוע ביותר אבל בהחלט קיים קנה מידה של "המקרה הממוצע" (הגדרת אותו מקרה ממוצע היא תחום מסובך שאין לי מושג בו). אבל בכל מקרה, גם עפ"י דעתו של עוזי וגם לדעתי הדוגמא הזאת אינה טובה שם. תומר א. - שיחה 15:20, 16 בספטמבר 2009 (IDT)

לא מדויק שזה לא מדויק. "זמן ריצה" של אלגוריתם על קלט באורך n הוא בוודאי זמן הריצה במקרה הגרוע ביותר. זה לא "זמן ריצה ממוצע". עוזי ו. - שיחה 22:59, 16 בספטמבר 2009 (IDT)

אני מצטט מהספר "אלגוריתמיקה" - יסודות מדעי המחשב מאת דוד הראל בהוצאת האוניברסיטה הפתוחה עמ' 141 בפסקה האחרונה כתוב: "לפיכך, ישנם אומדנים שימושיים אחרים לביצועי זמן של אלגוריתם, כגון התנהגותו במקרה הממוצע. כאן אנו מעוניינים בזמן הריצה הממוצע של אלגוריתם, כאשר לוחקים בחשבון את קבוצת הקלטים כולה ואת הסתברות הופעתו של כל קלט" ההמשך הוא התבכיינות על כמה קשה לחשב את אותו מקרה ממוצע חמקמק. בעמוד שלאחר מכן כתוב: "לעומת זאת, עבור כמה אלגוריתמים עשוי ניתוח המקרה הממוצע לגלות ביצועים טובים במידה משמעותית. הדוגמה הקלאסית לכך היא אלגוריתם מיון נוסף, שאותו לא נתאר כאן הנקרא מיון מהיר (Quick sort)". כהערת אגב אעיר שאותו מקרה ממוצע הוא הסיבה לשימוש באלגוריתם זה בישומים מעשיים על פני חבריו בעלי זמן הריצה הגרוע הטוב יותר. יחד עם זאת, אני לא חולק שבשפת היום יום כאשר אומרים "זמן ריצה" מתכוונים לזמן הריצה הגרוע ביותר וכדי להשתמש בזמן הריצה הממוצע יש צורך להבהיר זאת במפורש. תומר א. - שיחה 23:24, 16 בספטמבר 2009 (IDT)

הסבר פשוט ומובן

― הועבר מהדף ויקיפדיה:הכה את המומחה
יובל מדר - שיחה 23:07, 30 במאי 2011 (IDT)

מישהו יודע להסביר במילים פשוטות ומובנות מה זה בעיית P=NP? אני יודע שזה משהו שקשור לאלגוריתמים או משהו בסגנון. 79.181.211.215 20:00, 26 במאי 2011 (IDT)

ראה P=NP. עוזי ו. - שיחה 20:05, 26 במאי 2011 (IDT)

צריך ערך נפרד לבעיה. בניסוח חפיפניקי P היא קבוצת כל הבעיות שאפשר לפתור בזמן סביר (פורמלית, יש אלגוריתם שפותר את הבעיה בזמן פולינומי). NP היא קבוצת הבעיות שבהינתן פתרון להן, ניתן לוודא בזמן סביר כי הפתרון באמת נכון. ברור כי כל בעיה ב-P היא בעיה ב-NP. השאלה היא האם גם כל בעיה ב-NP היא בעיה ב-P (כלומר, P=NP). במילים אחרות השאלה היא האם כל בעיה שאנחנו יכולים לוודא בזמן סביר כי פתרון שמוצע לה הוא נכון, היא גם בעיה שניתן לפתור בזמן סביר. הדעה הרווחת היא כי התשובה היא לא, אבל כבר חמישים שנה שלא מצליחים להוכיח זאת, ויותר גרוע, אפילו לא מצליחים למצוא כיוון (ויותר גרוע, ניתן להוכיח כי השיטות המקובלות במדעי המחשב לא חזקות מספיק כדי לתקוף את הבעיה). הסבר טוב תוכל למצוא כאן. דניאל ב. • תרמו ערך 21:38, 26 במאי 2011 (IDT)

זה היה ערך נפרד זמן רב, והפך להפניה ללא דיון נראה לעין. עוזי ו. - שיחה 23:27, 26 במאי 2011 (IDT)

אני אוסיף רק דבר אחד שלעתים רבות מושמט בדיון על P=NP.
זה לא כזה חשוב!
מי שלמד מדעי המחשב ב-30 השנים האחרונות, מאוד מורגל לז'רגון הזה "פולינומי" אל מול "לא פולינומי" או "אקספוננציאלי" כפי שנוהגים פעמים רבות לתייג בעיות NP-שלמות.
הז'רגון משקף את מעמדה המיוחד של החלוקה הזו, בעבר!
בעבר חשבו שהחלוקה הנ"ל היא חלוקה שברגע אחד, תיתן לנו המון מידע על המון בעיות.
היינו, חשבו שמספיק למצוא האם בעיה היא ב-P, או שמא רק ב-NP, על-מנת לדעת אם היא "קשה" או "קלה" לפתרון.
במשך 15-20 השנים האחרונות, התפתח מדע הקירובים בתוך מדעי המחשב, בצורה בלתי-רגילה.
קיימות היום בעיות המוגדרות NP-שלמות, שלהן ישנם אחלה קירובים.
באופן פרקטי, אלו אינן בעיות קשות! באופן פרקטי ישנם מחשבים המריצים קוד שפותר בעיות אלו מדי יום, ומהר!
אינני יודע מה הסיבה לשגעון הנוכחי עם P=NP, אני מניח שזה בעיקר עניין של יוקרה. גביע קדוש שכזה.
בדיוק כמו להוכיח את המשפט האחרון של פרמה.

רק אוסיף ואומר שאינני מזלזל בסוגיה הנ"ל, אלא רק מציין שבעבר היא נחשבה פרקטית וחשובה באופן מעשי, והיום היא בתחום התיאוריה בלבד.
P או NP שתיהן חלוקות גסות מדי על-מנת למצות את טיב הבעיה.
וכן, קורס בחישוביות זה אחלה - Give it a try.
דוד הירושלמי - שיחה 02:55, 27 במאי 2011 (IDT)

דבריך לא כל כך מדויקים. בהחלט לא לכל הבעיות ה-NP קשות יש אלגוריתם דטרמיניסטי או הסתברותי שפותר אותן לפחות בקירוב. וגם אם כך היה, האלגוריתמים שאתה מתאר מאוגדים גם הם במחלקות סיביכויות שגם עליהן יש שאלות דומות בסגנון P=NP. לפתרון השאלה יש גם השפעה על שאלות מעשיות חשובות כמו יעילותה של הצפנה חד-כיוונית. דניאל ב. • תרמו ערך 15:55, 27 במאי 2011 (IDT)

אשרי המאמין :) - בוא נגיד שאם היינו פיסיקאים, כבר מזמן היינו אומרים ש-P!=NP.

יש בעיות שגם ה*קירוב* שלהן הוא NP (ואף NPC). עוזי ו. - שיחה 16:04, 27 במאי 2011 (IDT)

כמובן שאתה צודק - רק היה חשוב לי לציין, את שאמרת.
יש בעיות כאלה, ויש כאלה... גם בתוך מחלקת NPC.
זוהי חלוקה גסה מדי.
דוד הירושלמי - שיחה 18:21, 27 במאי 2011 (IDT)

אתם יכולים להסביר למישהו שלא מבין כלום במדמ"ח ואלגוריתמים מה כל מה שאמרתם אומר? 109.66.211.136 10:13, 28 במאי 2011 (IDT)

נקודה נוספת היא שבעיות פתירות פולינומית לא בהכרח באמת פתירות באופן מעשי. למשל, בעיה שזמן הריצה שלה הוא פולינום ממעלה 20 בלתי פתירה לחלוטין כבר עבור nים לא קטנים בכלל. למעשה, קיימות בעיות להן קיימים פתרונות פולינומיים, אשר לא משתמשים בהם בגלל שהם פולינומיים כבדים מדי. (למשל, פתרון לבעיית התכנון הלינארי) הטכנוקרט המזמר - שיחה 19:01, 28 במאי 2011 (IDT)

סליחה! סליחה! סליחה! באמת עפנו קצת רחוק.
מה לא הבנת?
או יותר פשוט מה כן הבנת?
אם לא הבנת דבר, אמור זאת - ונסביר טוב יותר.
לאיזו מן הקבוצות הבאות אתה שייך: תיכוניסט, חייל, אקדמאי, אדם רגיל המתעניין?
באם הנך אקדמאי, מאיזה תחום אתה מגיע: רוח, חברה, מדעים מדוייקים, מתמטיקה...?
דוד הירושלמי - שיחה 18:10, 28 במאי 2011 (IDT)

אתם מדברים על כל מיני בעיות מסובכות לא מסובכות או משהו בסגנון. קצת זכור לי מהתיכון שאת המוסג סיבוכיות מגדירים כמספר פעולות שצריך לבצע בשביל להגיע לתוצאה. נכון? וגם זכור לי קצת שסיבוכיות היא מאפיין של אלגוריתם ספציפי ולא של הבעיה עצמה- כלומר אחד יכול לעשות אלגוריתם יותר מסובך מהשני והם יגעו לאותה תוצאה. מקצת קריאה בערך הבנתי שפה מדברים לא על הפיתרון עצמו אלא על בדיקה של הפיתרון? מה זה אומר? ומה זה בעצם אותו "פולינומיאלי" , "אקספוננציאלי" וכדו' כמשברים על מדמ"ח? זה פונקציות מתמטיות מוכרות, אבל איך זה קשור לסיבוך? ומה הסימן של שיוון בשאלה אומר? "אלגוריתם שקל לפתח קל לבדוק" או אולי "אלגוריתם שקל להריץ קל לבדוק", "כמה שפחות פעולות ככה יותר קל לבדוק"? אין לי הרבה רקע מעבר מלכתוב לולאה מכוננת ורקורסיה פשוטה( שרוב הסיכויים תתקע לי...). 109.66.211.136 18:17, 28 במאי 2011 (IDT)

במשפט אחד: "שאלת P מול NP, שואלת האם בעיות שאנו יודעים שהן קלות [הסבר יגיע] הן למעשה קלות כמו בעיות שאנחנו מניחים שהן קשות [הסבר יגיע]".
זו ממש אינה ההגדרה הפורמלית, אך זה טוב מספיק בשלב זה.

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

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

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

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

השאלה האם P=NP, היא השאלה האם אי-פעם נמצא פתרון כזה. פתרון שיצליח לפתרון לנו בעיות "ברמת קושי NP", בצורה יעילה כמו "בעיות ברמת קושי P".

אני מקווה שהבנת את זה, אם כן - אפשר להתקדם, ותרגיש חופשי לשאול.
לקהל הצדיקים, אני מבקש לא להכנס לדקויות של NPC וכו', זה כל-כך לא הזמן.
דוד הירושלמי - שיחה 18:51, 28 במאי 2011 (IDT)

הסבר ממש וטוב. מהדברים שלך אפשר להבין שיש אפשרות לחשב יעילות של אלגוריתם לפני שהוא נכתב? כלומר הבניתן משימה "לחשב את אחוז התלמידים שעברו את החציון ב20% ומעלה" ( ניגד יש לך איזה מוסד נתונים עם כל הציונים) - אז בלי לכתוב את האלגוריתם עצמו אתה יכול לקבוע שהוא יהיה P? אם הוכחנו שכל הבעיות הקשות יכולות להיפתר כמו בעיות קלות (זה מה שזה אומר P=NP, לא?), האם זה עוזר לנו? כלומר- נגיד אני יודע שהבעיה שלי צריכה להיפתר בP. האם הידע הזה מסייע לי בפיתוח? 109.66.211.136 19:30, 28 במאי 2011 (IDT)

הרבה שאלות, אני אנסה לענות עליהן. לא בטוח שאצליח לענות על כולן.

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

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


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

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

אני מקווה שזה היה חצי מובן, לצערי אין לי כרגע הסברים חכמים יותר. דוד הירושלמי - שיחה 23:02, 28 במאי 2011 (IDT)
אה וצדקת לגמרי בהגדרה שלך:
אם הוכחנו שכל הבעיות הקשות יכולות להיפתר כמו בעיות קלות (זה מה שזה אומר P=NP, לא?)
אכן כן!
אני רק אוסיף ש-NP, היא מחלקה אחת בלבד של בעיות "קשות", יש מחלקות סיבוכיות שאנחנו יודעים בודאות שבעיות ששייכות אליהן - הן אפילו יותר קשות לפתרון מבעיות ב-NP.
ולכן גם אם נראה ש-P=NP, אין פירושו כי הוכחנו כי ניתן לפתור בקלות את כל הבעיות החישוביות הקשות, אלא רק חלק קטן מהן - אלו "ברמת קושי NP".
דוד הירושלמי - שיחה 23:08, 28 במאי 2011 (IDT)

נאמר כאן שיש מחלקות סיבוכיות רבות, וש-P ו-NP הן רק שתיים מהן. כדי שלא יווצר הרושם שבעיית P=NP חשובה רק מסיבות הסטוריות (ושאפשר היה לשאול עוד המון בעיות דומות וקשות באותה מידה), אני רוצה להעיר הערה עקרונית. המחלקה NP כוללת בעיות שאפשר *לזהות* ביעילות פתרונות שלהן: אם מישהו חולם פתרון, או מקבל אותו בשדר מאלפא קנטאורי, הוא יכול לבדוק האם הפתרון נכון, גם אם הוא אינו יודע לחשב פתרונות כאלה בעצמו. המחלקה P כוללת בעיות שאפשר *לפתור* ביעילות. השאלה האם P=NP היא על גבול הפילוסופיה (למרות שיש לה כמובן ניסוח מתמטי מדוייק): האם כל דבר שאפשר לזהות בדיעבד, אפשר לחשב גם לכתחילה? עוזי ו. - שיחה 16:54, 30 במאי 2011 (IDT)

חשיבות

לפי דעתי לבעיית P=NP יש חשיבות רבה בתחום מדעי המחשב ומגיע לנושא זה שיהיה לו ערך ולא רק פסקה בערך של מחלקת סיבוכיות NP. (מתייג את בעלי הידע במתמטיקהיונה בנדלאק, דניאל ב., hagay1000, פשוט, עוזי ו. (בנושאים מסוימים), דביר, איתי (לא בכל מה שקשור למתמטיקה), יואל, ruleroll (גאומטריה), רמי, Tshuva, בר, yotamsvoray, CodeGuru, Zardav, דוד שי, אכן, TergeoSoftware, MathKnight, מקף, E L Yekutiel, שגיא בוכבינדר שדור, YoavDvir, Meir2, Kivkiwi, Innaento, דימה, איתן, Vhinich, Shmoran ) Yotamsvoray - שיחה 13:05, 2 בספטמבר 2017 (IDT)

אפשר להתחיל מגרסה זו. פרינציפ (.a.k.a ראובן מ.) - שיחה 13:13, 2 בספטמבר 2017 (IDT)

נכון. אני פותח טיוטה:P=NP.‏ Yotamsvoray - שיחה 13:37, 2 בספטמבר 2017 (IDT)

חזק ואמץ! דוד שי - שיחה 13:40, 2 בספטמבר 2017 (IDT)

בהחלט כדאי. יגאל (בקשת עזרה, IKhitron ושיחה) 18:32, 2 בספטמבר 2017 (IDT)

בעד Tshuva - שיחה 07:42, 3 בספטמבר 2017 (IDT)

מה דעתכם על הטיוטה? האם אפשר להעלותה כערך או שיש דברים להוסיף. (מי שמעוניין מוזמן)Yotamsvoray - שיחה 16:25, 21 בספטמבר 2017 (IDT)

להעביר למרחב הערכים, תמיד אפשר יהיה לשפר את הערך שם. דוד שי - שיחה 19:51, 21 בספטמבר 2017 (IDT)

מצוין. אבל מה בנוגע לשם הערך? לא כדאי משהו יותר "מפורט", כמו P נגד NP כמו בויקיפדיה באנגלית? Yotamsvoray - שיחה 22:01, 21 בספטמבר 2017 (IDT)

שאלת P=NP או בעיית P=NP נראים לי עדיפים. דוד שי - שיחה 22:47, 21 בספטמבר 2017 (IDT)

דיווח על טעות

פרטי הדיווח

הקישור לSAT אינו נכון בהקשר של הערך. כאן מדובר על בעית ההכרעה SAT ולא על הבחינה האמריקאית דווח על ידי: 2.53.148.29 10:58, 27 במרץ 2020 (IDT)

תיקנתי. דוד שי - שיחה 11:06, 27 במרץ 2020 (IDT)