tag:blogger.com,1999:blog-3722233.post109872529202690967..comments2023-03-20T21:49:52.361-05:00Comments on Computational Complexity: What Would the Martians Think?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-1098842977652306082004-10-26T21:09:00.000-05:002004-10-26T21:09:00.000-05:00This reminds me of a talk by Jack Cohen, a reporod...This reminds me of a talk by Jack Cohen, a reporoductive biologist (interesting profession) that also does "alien species developement" for Sci-fi authors. His rule of thumb: Something that has happened a few times independently on Earth, will happen on other planets. For example, flying things (as birds and bats have no common flying ancestor). Things that happened once on earth, such as hair (all hairy creatures have one common hairy ancestor), are less likely.<br /><br />Applied to our subject, I guess this would translate to "classes discovered independently by more than one person are probably more natural". Time-constrained deterministic classes seem like such an example, but can we verify this criterion for others?<br /><br /> - Eldar.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098801052390363752004-10-26T09:30:00.000-05:002004-10-26T09:30:00.000-05:00Is it possible to look at this as through Kolmogor...Is it possible to look at this as through Kolmogorov complexity? I won't be as powerful a definition of "natural", but any class might be considered to be natural if we can describe it without actually writing an algorithm for it.<br /><br />The other way to look at it is like the old judge said "I don't know how to define it, but I know it when I see it."Brian Postowhttps://www.blogger.com/profile/04426675383041390587noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-1098731554364882902004-10-25T14:12:00.000-05:002004-10-25T14:12:00.000-05:00There is a big difference between the definition o...There is a big difference between the definition of 'natural' that Bill and Lance have been discussing -- easily explainable and justifiable to Martians and non-CS Earthfolk alike -- and the more useful, though somewhat fuzzy, notion of 'natural' typically used in complexity. <br /><br />Typically, a 'natural' problem is a problem that is defined without reference to a complexity class (or complexity bound). Therefore, for example, usual diagonal languages are not natural. However, the equivalence for regular expressions with squaring IS most certainly natural under this definition. This distinction allows us to phrase useful open questions: we can prove that there are problems in P requiring time complexity Omega(n^2) but can we find any natural problems for which we can prove this property? <br /><br />Lance also raises the question of what constitutes a 'natural' complexity class. I don't think anyone has a good answer for this. One might want to include any class for which there is a 'natural' complete problem but then what is the 'natural' notion of reduction under which the completeness holds? <br /><br />The question for complexity classes seems much more pragmatic than the standard notion of naturalness for problems: What is a good reason for someone to care about your complexity class?<br /><br />Paul BeameAnonymousnoreply@blogger.com