שיחה:NP (מחלקת סיבוכיות)

שלמות

יש לך חצי שגיאה בסעיף "NP-קושי ובעיות NP-שלמות". כתבת ש"אם יהיה ניתן להראות עבור בעיה NP-שלמה אחת כי היא אינה שייכת ל-P הדבר יגרור מייד כי P≠NP." וצ"ל "אם יהיה ניתן להראות עבור בעיה NP אחת כי היא אינה שייכת ל-P הדבר יגרור מייד כי P≠NP.".‏ Easy n - שיחה 15:04, 13 באוקטובר 2009 (IST)

"סתם" בעיות NP אינן מעניינות בהקשר הזה - המשפט ההוא מדבר בדיוק על המעמד המיוחד שיש לבעיות ה-NP-שלמות: לכל אחת מהן, התשובה לשאלה האם היא שייכת ל-P או לא שקולה לשאלה האם P=NP או לא. גדי אלכסנדרוביץ' - שיחה 19:11, 13 באוקטובר 2009 (IST)

הבעיה היא שהמשפט הזה הוא טאוטולוגיה. ברור שאם יש ב-NP שפה אחת שאיננה ב-P אז P≠NP וזה כלל לא חשוב אם אותה שפה נמצאת ב-NPC או לא. Easy n - שיחה 19:28, 13 באוקטובר 2009 (IST)

לא טענתי אחרת; אבל כאמור, המשפט הזה מסביר למה בעיות ב-NPC הן מעניינות; והן מעניינות כי עבורן מתקיימות שתי התכונות החשובות בו זמנית - הן שאם הן ב-P, אז P=NP (כי הן קשות, להבדיל מבעיות ב-NP שאינן NP-קשות) והן שאם הן לא ב-P אז P שונה מ-NP (כי הן ב-NP, להבדיל מבעיות קשות שאינן ב-NP). גדי אלכסנדרוביץ' - שיחה 19:31, 13 באוקטובר 2009 (IST)

ועוד אחת, בבעיית צביעת גרף צ"ל k>2. ‏Easy n - שיחה 15:09, 13 באוקטובר 2009 (IST)

צודק בהחלט. לזכותי ייאמר שסתם העתקתי והדבקתי, ומצד שני לחובתי ייאמר שסתם העתקתי והדבקתי. גדי אלכסנדרוביץ' - שיחה 19:11, 13 באוקטובר 2009 (IST)

"בעיה A תקרא NP-קשה אם ורק אם לכל בעיה B ב-NP קיימת רדוקציה פולינומית מ-B ל-A"

נראה לי שטות.

בעיה נמצאת בNP HARD אם קיימת רדוקציה מבעיה בNP?

צריך לתקן. Maromblu - שיחה 19:11, 26 בינואר 2022 (IST)

הערות

הנה רשימה של הערות, שיהיה להמשך.. לא הכל מצריך טיפול מיידי..

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

אולי גם לאזכר את ההגדרה הפורמלית לפי משפט ה-PCP.‏ Gran - שיחה 01:25, 15 באוקטובר 2009 (IST)

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

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

יהיה לזה מקום בפרק הנוסף שצריך לכתוב, על הקשר בין NP למחלקות אחרות (כמו שאמרתי, צריך לאזכר מתישהו את BPP ואת ההיררכייה הפולינומית). גדי אלכסנדרוביץ' - שיחה 22:26, 15 באוקטובר 2009 (IST)

ו. השלכות P=NP על הקריפטו אינו ברור. כנראה זו השעה.. :)
ז. החלקים של NP-שלמות וקושי יותר טובים מהשאר.
. בברכה, Gran - שיחה 06:24, 14 באוקטובר 2009 (IST)

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

אני מתנצל, זה עתה דרסתי שינויים שעשית בחלק הנוגע להגדרות, כי כתבתי אותו מחדש בעצמי. האם אתה רואה דרך/צורך לשלב אותם בגרסה החדשה שלי? גדי אלכסנדרוביץ' - שיחה 07:45, 14 באוקטובר 2009 (IST)

אופס, בכלל לא שמתי לב שאנחנו מתנגשים.. בצע כאוות נפשך - אני אסתכל על זה מחר. מצטער בשנית. Gran - שיחה 07:50, 14 באוקטובר 2009 (IST)

הרבה יותר טוב משלושה ערכים נפרדים. האם אני יכול לעבור עליו קצת ולשנות מעט ניסוחים? תומר א. - שיחה 14:16, 17 באוקטובר 2009 (IST)

בשביל זה זה כאן. שים לב שהמטרה של הערך הזה היא להחליף ארבעה ערכים: NP-קשה, NP-שלמה, NP (סיבוכיות) ו-P=NP. גדי אלכסנדרוביץ' - שיחה 14:35, 17 באוקטובר 2009 (IST)

אני לא בטוח אם צריך להחליף את P=NP. תומר א. - שיחה 18:24, 17 באוקטובר 2009 (IST)

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

אולי אתה צודק. תומר א. - שיחה 19:23, 17 באוקטובר 2009 (IST)

ח. רשום שלא ידוע פתרון בזמן פולינומי לפירוק לגורמים של מכפלה של שני ראשוניים, אבל זה בולשיט טוטאלי. אפשר לעשות את זה בזמן לינארי. אולי הכוונה היא לפירוק לגורמים של קודמים של שני ראשוניים? כי זו הכוונה מאחוריי RSA. --79.178.34.144 14:22, 18 במאי 2011 (IDT)

החול יזכור

היי גדי, נדמה לי שכדאי להעביר את הארגז למרחב הראשי, למזג את הערכים כפי שהתכוונו, ולתת לויקיפדים להמשיך משם.. Gran - שיחה 09:10, 28 באוקטובר 2009 (IST)

אוקיי, לעבודה. גדי אלכסנדרוביץ' - שיחה 10:55, 29 באוקטובר 2009 (IST)

טוב, צריך להעביר לNP (סיבוכיות) אבל למיטב הבנתי אני לא יכול לעשות זאת בלי הרשאות מפעיל, כי זה דורס את הדף הקודם (ויש לדרוס ולא סתם להעתיק כדי לשמור את היסטורית השינויים). מה עושים? גדי אלכסנדרוביץ' - שיחה 10:56, 29 באוקטובר 2009 (IST)

מבקש בויקיפדיה:בקשות ממפעילים או מחכה שמישהו עם הרשאת מפעיל יטפל בזה. תומר א. - שיחה 20:39, 29 באוקטובר 2009 (IST)

שינוי שם פסקת המבוא

השם שונה מ-"מבוא" ל-"האם P=NP? - מבוא בלתי פורמלי". אני סבור שהמצב הקודם עדיף. ראשית, פסקת המבוא אינה עוסקת במיוחד בשאלה האם P=NP אלא רק מזכירה אותה בסוף (כי לא יעלה על הדעת ששאלה זו לא תוזכר כלל במבוא). הפסקה מתמקדת באפיון של NP (בדיקה יעילה מבחינת סיבוכיות זמן ריצה). שנית, אני לא חושב שיש צורך לציין במפורש שהמבוא הוא "בלתי פורמלי" - זה טבעם של פרקי מבוא. גדי אלכסנדרוביץ' - שיחה 21:34, 13 בנובמבר 2009 (IST)

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

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

שחזור הפתיחה

שחזרתי את השינוי שבוצע בפתיחה. הסיבות לכך:

1. הוא הכניס בכוח מושגים "פורמליים" שאין סיבה להפיל על הקורא מייד בהתחלה ("פולינומיאלי"). למי שרוצה פורמליזם מייד בהתחלה יש את הקישור לסיבוכיות זמן ריצה.
2. הוא היה שגוי/מבלבל (ל-NP שייכת גם כל בעיה ב-P, ולכן להגיד ש"כוללת את הבעיות שהפתרון היעיל ביותר הידוע להן מתבצע בזמן על-פולינומיאלי" עלול לתת רושם שגוי שאין ב-NP בעיות פתירות).
3. הוא סילק את התואר "מעשיות" לבעיות ב-NP, אף שזו אחת הסיבות המרכזיות לכך שהבעיה הזו חשובה כל כך. גדי אלכסנדרוביץ' - שיחה 08:34, 14 בנובמבר 2009 (IST)

אין לי כח להתווכח עם זה אבל אני רק רוצה להגיד שלא מדובר כאן באנציקלופדיה לגיל הרך ואני לא רואה שום מניעה להכניס פורמליזם בסיסי בהתחלה. אם מישהו רוצה ללמוד ערכי מחשבים דרך ויקיפדיה שלא יתחיל בערך הזה. זה כמו להתחיל ללמוד אלגברה דרך הערך אידאל (אלגברה). ולא כל הבעיות במחלקה הזאת מעשיות וממילא לא רק המעשיות נחקרות. תומר א. - שיחה 11:21, 14 בנובמבר 2009 (IST)

למה שלא יתחיל בערך הזה? זה ערך על מה שהוא אחד מהמושגים הבסיסיים ביותר בתיאוריה של מדעי המחשב. זה הערך שאליו צריך לפנות כל מי ששמע על שאלת P=NP ורוצה עוד פרטים. זה בהחלט צריך להיות ערך נגיש לכלל, ולא רק למי שבקיא במושגים הטכניים. ואכן, לא כל הבעיות מעשיות ולא רק הן נחקרות, אך המעשיות הן אלו שהופכות את המחלקה למעניינת ורלוונטית. גדי אלכסנדרוביץ' - שיחה 11:41, 14 בנובמבר 2009 (IST)

הפסקה הנוספת (גדל, "עשרות חוקרים")

בטעות סילקתי גם את הפסקה ש-Gran הוסיף לערך:

"שאלה זו הוגדרה לראשונה בשנת 1957 כל ידי קורט גדל (אתר פרס גדל), ומאז מוגדרת בבעיה פתוחה מרכזית במדעי המחשב, ואחת מ"שבע בעיות המילניום" של מכון קליי למתמטיקה‏‏, אשר מציעים מליון דולר ארה"ב לפותר בעיה זו. עשרות חוקרים ([1]) הוכיחו תוצאות חלקיות אשר עשויות לרמוז על פתרונה של בעיה זו (עבור שתי האפשרויות), וכן קיימות עבודות אשר מציעות גכי בעיה זו אינה ניתנת להוכחה (אולי עקב אי-שלמות של מערכת ההוכחה שלנו."

אותה דווקא כדאי להחזיר, אבל:

1. צריך להיות זהירים במה שמייחסים לגדל (כרגע אין לי גישה ללינק, ולכן קשה לי להגיד משהו חכם יותר).
2. ה"עשרות חוקרים" בעייתי הרבה יותר, בגלל הלינק שלו; בלינק עצמו, בתחילת הרשימה, כותב מי שערך אותה ש"Among all these papers, there is only a single paper that has appeared in a peer-reviewed journal, that has thoroughly been verified by the experts in the area, and whose correctness is accepted by the general research community:" וזה בדיוק העניין. יש שם קשקושים מוחלטים (מאמר 8!). בפרט, אני מציע לסלק את ה"עבודות אשר מציעות כי בעיה זו אינה ניתנת להוכחה" עד שתנתן דוגמה למאמר רציני שטוען זאת, ובאופן כללי להיות חשדנים כלפי מי שמערב את משפטי גדל בעניין (כמובן, קיים סיכוי שאי אפשר להוכיח ב-ZFC ש-P שונה מ-NP או שווה לו, בדיוק כפי שקיים סיכוי שאי אפשר להוכיח בו את השערת רימן, השערת גולדבך, השערת בירץ' וסווינרטון-דייר וכל דבר אחר שתרצו. בכל אחד מהמקרים הסיכוי הזה הוא לא משהו שמתייחסים אליו יותר מדי ברצינות, ואין שום ייחוד ל-P=NP כאן). גדי אלכסנדרוביץ' - שיחה 08:43, 14 בנובמבר 2009 (IST)

הנה מאמר חביב ושקול הרבה יותר של סקוט אהרונסון (מה-Complexity Zoo) על עניין ה"לא ניתן להוכחה": [2]. גדי אלכסנדרוביץ' - שיחה 08:57, 14 בנובמבר 2009 (IST)

(הערה לעצמי: להמנע מכתיבה בשעות שצריך לישון בהם..). הוספתי את הפסקה מחדש, עם ניסוח הרבה יותר עדין. אין הוכחה, אבל לא ניתן להתעלם מכמות הנסיונות והמאמרים שפורסמו (גם אם כולם שגויים). לגבי הייחוס לגדל: זה מצויין מפורשות באתר הACM. לדעתי זה מקור אמין, אלא אם יש ראיות כנגדו. מודה שלא קראתי את המכתב של גדל, ואין לי ידע האם אכן נגע שם בבעיה, או רק בנושאים קשורים (שמהם ניתן להשליך על הבעיה). Gran - שיחה 21:42, 14 בנובמבר 2009 (IST)

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

למרות שעידנת מאד מאד (מאד), אני דווקא מרוצה מאיך שזה יצא. ועל מנת לסיים את הנושא, ראה [3]. מה יש עוד לומר... :) Gran - שיחה 02:43, 16 בנובמבר 2009 (IST)

גם 24 נחמד: הוא פותר את הבעיה, עד לשלב שבו "what remains to be done is technical work along the lines of traditional combinatorics", ואז עוצר. עוזי ו. - שיחה 22:21, 14 בנובמבר 2009 (IST)

בעיות פתוחות במדעי המחשב

נראה לי שכדאי להוסיף קטגוריה של בעיות פתוחות במדעי המחשב, לדוגמה בעיית העצירה, P=NP וכו'. וגם לכתוב משהו על הפרסים הכספיים המוצעים למי שיפתור בעיות כאלה. משתמש:אנונימי 51 - שיחה 21:41, 25 באוגוסט 2010 (IDT)

לגבי בעיית העצירה הוכח שהיא לא ניתנת לפתרון. היא לא פתוחה. תומר - שיחה 14:43, 11 במאי 2011 (IDT)

בעיה

בעיה בהתחלה"ידועה כשאלה "האם P=NP"; שאלה זו היא אחת מהבעיות הפתוחות המרכזיות במדעי המחשב," הוכח לפני כמה חודשים ע"י ד"ר מאוניברסיטה העברית כי p!=np לעיונכם הודעה זו נכתבה באמצעות מערכת המשוב. 
87.68.213.103 21:54, 30 באוגוסט 2011 (IDT)

אין כיום אדם שיודע איך בכלל לגשת לפתרון הבעיה הזו. דניאל ב. • תרמו ערך 21:59, 30 באוגוסט 2011 (IDT)

"קשרים עם מחלקות סיבוכיות דומות"

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

1. ההיררכייה הפולינומית.
2. BPP (למשל, שהכלה תגרום לקריסה בהיררכייה הפולינומית).
3. P/poly (שוב, התמוטטות ההיררכייה במקרה של הכלה; מה שנקרא משפט Karp-Lipton).
4. אי-הכלה ב-BQP (לפחות ביחס לרוב האורקלים).
5. הכלה טריוויאלית ב-PSPACE (אולי כחלק מהחלק על הההיררכייה).
6. משפט ה-PCP.

אפשר למצוא בגן החיות רפרנסים טובים (אני מניח שהרוב מתואר ממילא בספר של Arora ו-Barak).

(לא, אני לא אעשה את זה בעצמי, תודה ששאלתם) גדי אלכסנדרוביץ' - שיחה 10:51, 10 ביוני 2012 (IDT)

אם נדרת שלא לערוך במרחב הערכים, הנני להודיעך כי בתוקף סמכותי כרב הראשי לוויקיפדיה והסביבה, נדרך מותר. דוד שי - שיחה 22:25, 10 ביוני 2012 (IDT)

התמונה בראש הערך

לפי התמונה בראש הערך, אין חפיפה בין בעיות P לבעיות NP. אבל אם אני מבין נכון את הכתוב בערך, בעיות NP אמורות להכיל את כל בעיות P: "ידוע כי NP מכילה כל בעיה השייכת ל-P ... השאלה המהותית היא אם הכלה זו היא הכלה ממש, כלומר, אם קיימות בעיות ב-NP שאינן ניתנות לפתרון יעיל, או שמא כל בעיה ב-NP ניתנת גם לפתרון יעיל". אם לא טעיתי, קבוצת NP בתמונה צריכה להכיל את קבוצת P, והשאלה היא האם היא רק מכילה את קבוצה P, או שהיא ממש זהה לה. כרגע התמונה מראה מקרה כללי/קיצוני יותר, שלפיו בעיות P אינן דווקא NP, בניגוד לכתוב. 77.126.77.238 19:02, 25 בנובמבר 2016 (IST)

החלפתי תמונה. דוד שי - שיחה 08:12, 26 בנובמבר 2016 (IST)

תודה 77.126.77.238 20:09, 27 בנובמבר 2016 (IST)

בעיית הסוכן הנוסע אינה בNP

בחלק מהערך "תרבות" מופיע המשפט "שם הסרט נלקח מבעיית הסוכן הנוסע, שנכללת במחלקת הסיבוכיות NP". להבנתי בעיית הסוכן הנוסע אינה נכללת במחלקה NP, אלא נחשבת NP-HARD, וכך גם כתוב בערך על בעיית הסוכן הנוסע. ‫192.114.91.248‬ 10:38, 30 ביוני 2024 (IDT)

תיקנתי. דוד שי • שיחה 12:31, 30 ביוני 2024 (IDT)