יו ידידיי הניגרוס - כבכל יום לפני מבחן אני וידיד הניגרו פה אם-סי-woo יושבים ופותרים מבחנים, ונתקלנו בשאלה שאין לנו שמץ למה התשובה עליה נכונה - ובגלל שזה אמריקנו אז גם אין לנו איך לדעת.. קיצר השאלה בנושא, אבל אם משום מה פספסתם אז הנה: אם NL=P, למה מתקיים ש- EXP=Pspace, לצורך העניין למה לא מתקיים ש Space(log2n)=P ? בגלל שזה הכלה ולא שיוויון בין NL ל- Space(log2n) ?
ד"א הקטע הזה של הפיירפוקס מונע גישה אל החוצץ ממש מטריד - אני עושה פייסט עם shift+insert כדי לעקוף את זה אבל זה קקי בקי שקי לקי נקי (?)
my two cents
Melnorme
(סיבוכיות)
29.06.2006 14:09
אני די בטוח ש EXP במבחנים זה EXPTIME כיוון ש PSPACE = NPSPACE זה פשוט padding argument
