שְׁאֵלָה:
מה היה הרומן הראשון שהתרחש ביקומים שבהם P = NP?
Dr G
2011-01-12 03:43:30 UTC
view on stackexchange narkive permalink

מעניין אם מישהו כתב רומן המתרחש ביקום שבו P = NP , במקרה שיש יותר מאחד, שהיה הראשון?

enter image description here

ביקום זה ניתן לפתור את כל הבעיות שניתן לאמת בזמן הפולינום (נתון הפיתרון) בזמן הפולינום (P).

מסיבה טובה, הייתי מדמיין. אני יכול לראות את הדיאלוג עכשיו.
גרג איגן כתב מספרים שלמים כהים ו- Luminous העוסקים בחישוב ובמורכבות בהגדרות אלגברה טהורה. אם זה יכול לעבוד, כך גם רומן על P = NP :)
לא רומן, אבל ראסל אימפאגליאצו (חוקר תורת המורכבות המובילה) כתב מאמר קצר המתאר חמישה עולמות שבהם דברים כאלה קורים (ביקום האלגוריתמיקה יש P = NP, Cryptomania הבטיחה הצפנת מפתח ציבורי וכו '). רק חשבתי שאזכיר למקרה שאתה סקרן לנקודת מבט תיאורטית יותר על איך נראה עולם עם P = NP. http://blog.computationalcomplexity.org/2004/06/impagliazzos-five-worlds.html
ד"ר G +1, אבל אני לא בטוח אילו גרסאות לסיפורים הקצרים של איגן קראת: P אבל אני ראיתי את זה כאילו ערכי האמת של הצהרות חשבון מתנהגים כמו סיבוב של חלקיק קוונטי, וחישוב של מתמטיקה התוצאות היוו את ערכי האמת הללו, לרעת "יקום אחר ומקביל". הפיזיקה עצמה הושפעה משינוי כללי המתמטיקה, ולכן היה כאוס מסביב כאשר 'האחרים' נלחמו חזרה. (וכן, יש לי דוקטורט במתמטיקה טהורה)
... ואיך יודעים ש- P = NP אינו נכון היקום שלנו? הודע לי ואני אחלוק איתך את מיליון הדולרים.
@DavidRoberts הייתי צריך לנסח את השאלה כרומן המתרחש ביקום בו אנו מכירים P = NP :) Re: איגן, פירשתי את הסיפור כטוויסט על ההגדרה המתכוונת. התיאוריה שלנו מבוססת על הגדרה מתכוונת, אין פירושה שהיקום מסכים, ומכיוון שלא ניסינו לאמת את הגרסה המרחיבה של ההגדרות שלנו, היקום הפיזי עשוי לחלוק.
אולי כולם ... מכיוון שזו בעיה לא פתורה ברגע זה. :-)
[דף הבית של מתמטיקה] (http://kasmana.people.cofc.edu/MATHFICT/) יהווה נקודת התחלה טובה למשהו כזה.
האם אתה יכול להסביר, במילים פשוטות * ממש *, מה פירוש P = NP וכיצד נדע אם ספר שאנו קוראים יהיה ביקום זה?
@Wikis: ביקום P = NP _מציאת_ פתרון נכון להיררכיית בעיות גדולה ומוגדרת היטב יהיה מורכב רק כמו _הכרה_ שפתרון מוצע לבעיה כזו הוא נכון. לדוגמא, ביקום שלנו להכיר בכך שיצירת אמנות היא נהדרת נראה הרבה יותר קל מאשר ליצור יצירה נהדרת. ביקום שבו P = NP כמות המאמץ הנדרשת תהיה זהה או רק צנועה יותר במבט מבחינת גודל הבעיה שיש לפתור. פיצוח קל של כמעט כל צורות ההצפנה הוא סימן נוסף ליקום P = NP.
@DrG: גרג איגן יכול כנראה לכתוב רומן שבו P ו- NP הם הגיבורים. הבחור הזה גורם לקים סטנלי רובינסון להיראות כמו ג'ורג 'לוקאס.
עשר תשובות:
#1
+75
Kyle Jones
2012-01-05 06:12:59 UTC
view on stackexchange narkive permalink

מסע בין כוכבים, אמנים שונים, 1966 (התרחשות מוקדמת ביותר)

P = NP ביקום מסע בין כוכבים, אך האנשים שם אינם מודעים לכך. עדות:

  1. יש הצפנה אך היא תמיד שבירה. P = NP יאפשר לך לפצח הכל מלבד רפידות חד פעמיות אך הפדרציה ממשיכה בעקשנות להשתמש בצפנים מבוססי NP.

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

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

  4. אינטליגנציית מכונה מודעת לעצמה נוצרת בקלות. ווסלי קרשר יצר אחד במקרה. כך גם ריצ'רד דייסטרום. מחשב ה- Enterprise D בישל את Moriarty במחזורי החילוף שלו, ד"ר Farallon יצר את Exocomps וכן הלאה. כל מה שנראה שאתה צריך לעשות זה לבנות משהו שווה ערך למערכת הוכחת משפט ולתת לה לרוץ מספיק זמן כדי להכשיל את ההוכחה ש- P או כל סוג אחר הניתן לביצוע שווה ערך ל- NP והמערכת יוצאת למירוצים.

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

+1 לשימוש בראיות מהעולם כדי להראות משהו כלשהו. הכי מוצלח.
אני חושב שהם פשוט מתמודדים עם שלוש הנקודות שאתה מנפיק בכוח מחשוב גולמי. DTM יכול לפתור בדיוק את אותן בעיות כמו NTM, אך זה לוקח זמן רב יותר. לכן, אם הכישורים ההנדסיים שלהם מטורפים מספיק, הם יכולים להשתעל במחשבים מהירים (מקבילים) (גם הם כנראה מצאו כמה יוריסטיות נחמדות לכמה בעיות קשות NP בדרך). אז אני לא בטוח כיצד הוויכוחים שלך חלים.
@Blue אולי הייתי צריך לכתוב P = NP מאפשר לך לפצח הכל _ שימושי_ אבל רפידות חד פעמיות. אם אינך יכול לאמת את הפענוח בזמן הפולינום, כלומר המשמעות של קיום מערכת קריפטה מחוץ ל- NP, אז גם עם הפענוח מפתח_ אין אפשרות לבצע חישובית. זו בעיניי לא מערכת קריפטה שימושית.
@bitmask: זה איפשהו במדריכים הטכניים שסטאר טרק מריץ את ליבת המחשב בתוך שדה עיוות שונה בו הזמן רץ בקצב אחר.
@MichaelEdenfield: אם * יש * טכניקות לפתרון בעיות חזקות יותר מאשר DTM מהיר מאוד, וליישומים מעשיים P ו- NP איבדו רלוונטיות, זה כשלעצמו עדות חזקה מאוד ל- P = NP ביקום. ביקום P! = NP הגילוי של טכניקות כאלה הוא מאוד לא סביר.
@Tynam P ו- NP מוגדרים בקפדנות במונחים של מה שאפשר לעשות עם מכונות טרניג דטרמיניסטיות ולא דטרמיניסטיות; פשוט אין טעם לדבר עליהם מחוץ להקשר זה. יש כבר עדויות לכך שמחשבים קוונטיים * עשויים * לספק דרך לבצע חישובים לא דטרמיניסטיים, למשל ...
@MichaelEdenfield: נקודה טובה; לא חשבתי דרך זווית המחשב הקוונטי / NDTM. עם זאת, ההבדל המעשי בין יקום P = NP לבין יקום מחשוב ND בעל עוצמה משמעותית נראה ככל הנראה קטן (אבל אז, אני לא משוכנע שהמוח האנושי חזק משמעותית מ- DTM; מקבילות אינה אותו דבר כמורכבות אלגוריתמית.)
אתה יכול לשים תאריך לזה?
תאריך @AncientSwordRage למה?
@Kyle התאריך שבו לדעתך סדרת מסע בין כוכבים הוצגה לראשונה כ- P = NP.
@AncientSwordRage בבחירת הדוגמאות שלי אני חושב שזה יהיה צריך להיות הפרק הראשון שמציג שימוש במתרגם האוניברסלי במצב מגע ראשון.ב- TOS זה יהיה פרק 10 של העונה הראשונה, "תמרון הקורבומיטים" כאשר * Enterprise * נתקל בבאלוק ובכדור הכיף של הפדרציה הראשונה.
@kyle שעושה את זה 1966, שהוא מתמודד.האם היית מתנגד לכך שאערוך אותו בתשובתך?
@AncientSwordRage לא, קדימה.
#2
+54
Martha F.
2011-01-13 08:33:59 UTC
view on stackexchange narkive permalink

נוגדנים, צ'ארלס סטרוס, 2000

סיפור קצר התלוי בעובדה שפתרון P = NP הוא תנאי הכרחי לפיתוח מודיעין מחשבים. זה זמין בספרו טוסט . Stross העלה את הטקסט המלא של ספר זה לרשת. ( קישור זה ייקח אתכם ישירות לסיפור.)

ולפי האתר של סטרוס, הסיפור היה:

פורסם ב- Interzone # 157; פורסם מחדש ב "השנה המדע בדיונית הטובה ביותר מס '18" (עורך גרדנר דוזואה). הוזכר ב"רשימת הקריאה המומלצת "של לוקוס לשנת 2000. רשימת המועמדים לפרס תיאודור סטרג'ון לשנת 2001 (הפסידה ל"סיפורו של טנדולו" של איאן מקדונלד).

#3
+25
deworde
2011-09-26 04:42:50 UTC
view on stackexchange narkive permalink

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

#4
+18
Mike Scott
2011-01-13 13:20:03 UTC
view on stackexchange narkive permalink

בסדרה "אזורי מחשבה" של Vernor Vinges ("הלהט"), אש על העמוק , עמקה בשמיים וה ילדי השמיים ), החישוב קל יותר בחלקים מסוימים של הגלקסיה, ומאפשר דברים כמו בינה מלאכותית ונסיעה ב- FTL.

הועלו השערות (אך אין שום עדות ישירה בספרים) כי P = NP באזורים אלה.

האם יש ראיות עקיפות? זכרוני הוא שחישוב שונה מחוץ לאזור האיטי (התזה של הכנסייה מתקיימת רק באזור האיטי) ומשהו כמו P = NP לא צריך להחיל או אפילו להיות הגיוני שם.
ב * A Fire Upon the Deep * רוכבי Skode מוצאים את האמונה של פאם בהצפנת המפתח הציבורי כהומוריסטית. מכאן אנו יכולים להסיק ש- 'P == NP' במעבר.
לא בהכרח - מחשבים קוונטיים יכולים להתמודד באופן תיאורטי עם בעיות שלמות NP בזמן הפולינום, גם ללא P = NP.
לא הם לא יכולים. הפעולות שהאלגוריתמים של הצפנת המפתח הציבורי הנפוצים ביותר מסתמכות עליהן הן קשות - פקטורינג, יומן דיסקרטי - אינן הושלמו (האמינו שהן) NP. אלה הבעיות שמחשבים קוונטיים מסוגלים באופן תיאורטי לשבור בזמן הפולינום. עם זאת, ישנם אלגוריתמי הצפנה של מפתח ציבורי ש * מבוססים * על בעיות שלמות NP, אך אלה אינם בשימוש נרחב (עדיין ...)
@BlueRaja כרגע איננו יודעים דרך להשתמש במחשב קוונטי כדי לפתור בעיות שלמות NP בצורה יעילה, אך אתה טוען כי 'P
@Code: כן, מצטער שלא דיברתי בזהירות. התכוונתי שזה * לא * ידוע (או מאמין) שזה אפשרי תיאורטית.
התכוונתי לומר אזורי מחשבה. אני לא בטוח שזה ממש נכון ש- P = NP, בכך ש- בכל מיקום מסוים באזור_, האינטואיציה שלנו שאתה יכול לבנות בעיה NP שלא תוכל לפתור בקלות מתקיימת. אבל אני חושב שזה מספיק דומה בכדי שראוי להזכיר, בכך שאתה יכול לעבור (או לשלוח הודעה) לאזור גבוה יותר, שם הבעיה שלך תהיה ניתנת לפיתרון בקלות.
#5
+5
M.K.
2011-05-26 03:51:45 UTC
view on stackexchange narkive permalink

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

זה לא הגיוני. בעיה שייכת ל- P, אם קיימת מכונת טיורינג מסוימת הפותרת בעיה זו (ההגדרה של NP דומה). לא משנה אם ישנם אמצעים אחרים שניתן להעלות על הדעת לפתרון בעיה זו. על ידי פריצת לולאות זמן הארי עבר מעבר לשאלה P = NP.
כן, אם המבחן שלו הצליח, פירוש הדבר שיש מכשיר חישוב 'חזק' יותר ממכונת טיורינג ולכן הוא הפריך את התזה של צ'רץ '. אז אם תשאיר את NP המוגדרת באמצעות מכונות טיורינג, זה לא היה מוכיח 'NP = P'.
IIRC, הוכח כי P = PSPACE (שהוא חזק יותר מ- P = NP) עבור מכונת טיורינג המצוידת ביכולת לשלוח נתונים אחורה בזמן, גם אם היא כפופה לעקביות עצמית של נוביקוב.עדיין יתכן ש- P = PSPACE למכונות טיורינג רגילות, אך זה נחשב אפילו פחות סביר מ- P = NP על ידי תיאורטיקני המורכבות 'המיינסטרים'.
#6
+2
Broklynite
2016-02-16 17:57:07 UTC
view on stackexchange narkive permalink

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

#7
+1
Gelvis
2011-01-13 22:16:51 UTC
view on stackexchange narkive permalink

נמסיס, אייזיק אסימוב, 1989

הוא מדבר על אי-אפשרות ועל השלכותיו של יקום בו חוקי הפיזיקה אינם חלים

אנא ספק תאריך עם תשובתך בפעם הבאה והסבר מדוע זה קשור * במפורש * ל- P = NP.
#8
+1
aquaherd
2011-09-21 05:37:04 UTC
view on stackexchange narkive permalink

אפקט התרגול , דייוויד ברין, 1984

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

אנא [ערוך] מדוע אתה חושב שזה המקרה.
#9
  0
jersey
2018-08-02 08:53:13 UTC
view on stackexchange narkive permalink

בסיפור Starshield Sentinels מאת מרגרט וייס וטרייסי היקמן, היו מחשבים / אינטליגנציות מלאכותיות שיכולות לענות על כל שאלה באופן מיידי על ידי שליחת השאלה בזמן חזרה לעצמה , נותן לו 'זמן' לפתור את זה. הטרחה היחידה לכך היתה שהמחשב היה צריך להיות 'ער' מספיק כדי לפתור אותו (משהו כמו Deep Thought ממדריך הטרמפיסט לגלקסיה שנדרש 10 מיליון שנים כדי לפתור את השאלה לחיים, ליקום ולכל דבר).

אמנם אני לא יודע אם זה נוגע בדיוק לכל דבר P = NP, אבל זה פותר את סעיף המשתנה / לפתור בשאלה.

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

#10
-2
Michael Kohne
2011-09-27 06:38:38 UTC
view on stackexchange narkive permalink

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

איך זה קשור ל- p = np?


שאלה ותשובה זו תורגמה אוטומטית מהשפה האנגלית.התוכן המקורי זמין ב- stackexchange, ואנו מודים לו על רישיון cc by-sa 2.0 עליו הוא מופץ.
Loading...