בתשובה לשוטה הכפר הגלובלי, 22/09/05 16:28
אפילו יותר מבולבל 332059
ברקת • בתשובה לשוטה הכפר הגלובלי שבת, 24/9/2005, 21:18
מה אם n=1 ?

_____________
ברקת, 3 יחידות מתימטיקה פלוס העתקה בבגרות.
אפילו יותר מבולבל 332125
אביב י. • בתשובה לברקת יום א', 25/9/2005, 3:47
הא! כבר סיפרו באייל את הבדיחה הזאת. בדיחות שמספרים יותר מפעם אחת, חובה להרוס :)

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

הסבר בעיית P=?=NP ב-‏30 שניות (מהזיכרון ועם נסיון להמנע מהגדרות פורמליות):

P היא מחלקת‏1 השפות‏2 המתקבלות‏3 ע"י מכונות טיורינג‏4 דטרמיניסטיות‏5 בזמן פולינומיאלי‏6.

NP היא מחלקת השפות המתקבלות ע"י מכונות טיורינג לא-דטרמיניסטיות‏7 בזמן פולינומיאלי.

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

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

______
‏1 מחלקה זו מן קבוצה גדולה שכזו.
‏2 שפה זה אוסף של מילים הכתובות באיזה א"ב סופי.
‏3 "שפה שמתקבלת ע"י מ"ט M" זה אוסף של מילים כך שעבור כל מילה המכונה M תעצור ותקבל אותה (ז'תומרת המכונה תעצור ותגיד לנו "חביבי, המילה שנתת לי היא בסדר היא").
‏4 מ"ט זה בסה"כ מן מחשב פרימיטיבסקי שכל מה שיש לו זה אוסף סופי של מצבים וזיכרון (סרט עליו הוא יכול לכתוב ולקרוא).
‏5 דטרמניסטית משום שבהינתן רגע נתון במהלך החישוב בו "מצב המכונה+האות עליה מביטה המכונה" (בקיצור: קונפיגורציה) בו היא נמצאת - תמיד מוגדר לה מה היא צריכה בדיוק לעשות והיא תמיד עושה בדיוק את זה (במילים אחרות: יש לה פונקציית מעבר דטרמניסטית).
‏6 ז"א בזמן החסום ע"י פולינום כלשהו. או במילים פשוטות: מהר יחסית (בניגוד לריצה בזמן אקספוננציאלי).
‏7 מכונה נוירוטית שיכולה "לנחש" במהלך החישוב, בהיותה בקונפיגורציה מסוימת, לאיזה מצב מתחשמק לה לקפץ לפני ביצוע צעד החישוב הבא. מילה מסוימת מתקבלת ע"י מכונה כזאת אם קיימת סידרה *כלשהי* של צעדים/ניחושים שיובילו את המכונה מהמצב ההתחלתי אל המצב המקבל. השפה המתקבלת היא אוסף כל המילים המתקבלות ע"י המכונה הזאת. על פניו נראה כאילו מ"ט כאלה הן הרבה יותר מהירות ממכונות "רגילות" (דטרמניסטיות).
אפילו יותר מבולבל 332126
אביב י. • בתשובה לאביב י. יום א', 25/9/2005, 3:52
ב-‏3 צריך להיות "שעבור כל מילה *בשפה*, המכונה M...".
אפילו יותר מבולבל 332210
. • בתשובה לאביב י. יום א', 25/9/2005, 13:38
לדעתי, בקצרקורס-מזורז-רצחים עדיף להשתמש בהגדרה אחרת ל־P ו¯NP (שקולה):‏
P היא קבוצת הבעיות שניתן למצוא להן פתרון ביעילות (בזמן פולינומי).
NP היא קבוצת הבעיות שניתן לוודא ביעילות האם משהו הוא פתרון שלהן או סתם קשקוש.

בהצגה הזאת, כל בר דעת מבין ש־NP הרבה יותר גדולה מ־P, וקולט את התסכול של מדעני המחשב שכבר 40 שנה לא מצליחים להוכיח כזה דבר ברור.
אפילו יותר מבולבל 332244
אביב י. • בתשובה ל. יום א', 25/9/2005, 15:20
אכן, גם אני אוהב יותר את הפשטות שבההגדרה הזאת של NP, אם כי אני לא שותף להרגשה שנביעת גודלה של NP מכך זה "כזה דבר ברור" (אם כי אני לא בטוח שבר דעת אנוכי).

אבל אולי כדאי לחזור לנושא הדיון המעניין, לפני ששדמי יצוץ פה ויוכיח ש-NP מוכלת *ממש* ב-P, באמצעות מ"ט בעלת קבוצת מצבים מלאה.
אפילו יותר מבולבל 332317
האייל הצעיר • בתשובה לאביב י. יום א', 25/9/2005, 19:38
הערה לגבי ‏1: במקרה הזה "מחלקה" היא באמת קבוצה (שלא כמו "מחלקת כל הקבוצות", למשל). היא אפילו די קטנה. העוצמה שלה היא א_0.
אפילו יותר מבולבל 332344
אביב י. • בתשובה להאייל הצעיר יום א', 25/9/2005, 21:19
וואלה.
אפילו יותר מבולבל 332321
ברקת • בתשובה לאביב י. יום א', 25/9/2005, 19:52
פשששששי... אתה מנסה להחזיר לי על הפעם ההיא שניסיתי להסביר לך מה זה פוסט מודרניזם? :-)
אפילו יותר מבולבל 332343
אביב י. • בתשובה לברקת יום א', 25/9/2005, 21:12
בטח :)
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות