tag:blogger.com,1999:blog-3722233.post5468069270589011298..comments2024-08-03T11:58:59.111-05:00Comments on Computational Complexity: E versus EXPLance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-3722233.post-75281424510003513152024-07-07T15:35:46.840-05:002024-07-07T15:35:46.840-05:00This reason we don't have a class for linear t...This reason we don't have a class for linear time is that the notion is model-dependent: there are languages that are linear time on a multi-tape Turing machine but require quadratic time on a single-tape Turing machineAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-28838977666389090322024-06-27T09:53:22.140-05:002024-06-27T09:53:22.140-05:00There's definitely similar issues with log spa...There's definitely similar issues with log space vs polylog space, and to lesser extent with P vs Linear. The challenge with E and EXP is that people will often just say "exponential time" to mean either class where we don't usually have that confusion with the other classes.Lance Fortnowhttps://www.blogger.com/profile/06752030912874378610noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-71496143087949631772024-06-27T08:56:07.831-05:002024-06-27T08:56:07.831-05:00I have the opposite question - why aren't ther...I have the opposite question - why aren't there similar distinctions on other levels of complexity?<br /><br />Why aren't we talking much of LINEAR (like P, but O(n)), what about "small versions" of L, NL?<br /><br />Why is E so special?Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13005626353250830282024-06-26T11:47:55.364-05:002024-06-26T11:47:55.364-05:00Like this postLike this postAnonymousnoreply@blogger.com