I prefer to use the Martian rule. Suppose we find a Martian civilization at about the same level of scientific progress that we have. If they have a concept the same or similar to one of ours than that concept would be natural, having developed through multiple independent sources.
Of course we don't have a Martian civilization to compare ourselves with so we have to use our imagination. I firmly believe the Martians would have developed the P versus NP question (or something very similar, assuming they haven't already solved it) making the question very natural. On the other hand I suspect the Martians might not have developed a class like LWPP. Other classes like UP are less clear, I guess it depends whether the Martians like their solutions unique.
Applying the Martian rule to Gasarch's post, WS1S is probably more natural than regular languages without squaring that equal Σ*. At least my Martians would say that.
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.
ReplyDeleteTypically, 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?
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?
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?
Paul Beame
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.
ReplyDeleteApplied 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?
- Eldar.