Car-tech

HP חוקר טוען פיצול קומפלקס מורכבות

אידיאל החירות – דקארט ושפינוזה | ד"ר נועה נעמן צאודרר

אידיאל החירות – דקארט ושפינוזה | ד"ר נועה נעמן צאודרר
Anonim

בעוד Hewlett-Packard reels מ את הנשורת של מנכ"ל מארק הרד יורד, החברה יכולה להתחמם על התהילה של לפחות הישג אחד פוטנציאלי חיובי: חוקר HP הציע את מה שהוא אומר הוא פתרון אחד הבעיות הקשות ביותר במדעי המחשב. המדען הראשי של HP Labs, Vinay Deolalikar, פרסם את מה שהוא טוען שהוא פתרון למה שמוכר באופן נרחב כבעיית ה- P לעומת NP.

אז זה בלתי מתקבל על הדעת כי בעיה זו היא כי המכון מתמטיקה קליי נשבע להעניק את מי פותר את זה בארה"ב 1 מיליון דולר. זהו אחד מתוך שבע בעיות בלבד, הידועות בשם "בעיות המילניום", המכון הציע את השפע הזה. אחת השבע, השערת Poincaré, נפתרה באופן רשמי ב -2006.

עדיין לא ברור אם Dolalikar יקבל את הכסף, שכן קליי לא אמר שהיא רואה את הבעיה נפתרה.

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

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

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

ג'ואב ג'קסון מכסה את התוכנה הארגונית והטכנולוגיה הכללית שבירת חדשות עבור

שירות החדשות של IDG

. בצע יואב בטוויטר ב @ Joab_Jackson. כתובת הדואר האלקטרוני של יואב היא [email protected]