בתשובה לגדי אלכסנדרוביץ', 16/08/10 11:27
P!=NP 623229
החוסם מטקסס • בתשובה לגדי אלכסנדרוביץ' יום א', 6/10/2013, 1:09
החסם של nlogn למיון הוא ב"מודל ההשוואות" שהוא מודל מוגבל (אסור להסתמך על הייצוג של המספר). לא ידוע חסם תחתון סופר-ליניארי למיון במודל הרגיל של מעגלים בוליאנים (או מכונות טיורינג). בעצם, לא ידוע (לי על) חסם תחתון כזה לאף בעיה!
P!=NP 623277
אא • בתשובה להחוסם מטקסס יום ב', 7/10/2013, 2:46
קל לחשוב על בעיה ("חשב את הייצוג האונרי של x הנתון בייצוג בינארי") שהפלט שלה סופר-לינארי, ולכן גם זמן החישוב.
P!=NP 623279
החוסם מטקסס • בתשובה לאא יום ב', 7/10/2013, 8:38
זה רק אחד ממגוון ניטפוקים אפשריים על מה שכתבתי. בוא(י) נחליף "בעיה" ב- "שפה ב- NP"? אני עוד מפסיד עליך פה.
חזרה לעמוד הראשי המאמר המלא
מערכת האייל הקורא אינה אחראית לתוכן תגובות שנכתבו בידי קוראים
האייל הקורא RSS מאמרים | כתבו למערכת | אודות האתר | טרם התעדכנת | ארכיון | חיפוש | עזרה | תנאי שימוש © כל הזכויות שמורות