[My Computational Complexity Web Log] What Would the Martians Think?
In Bill Gasarch's post last week, he discusses what makes a problem natural. You used to hear the argument that a complexity class was natural if it contained an interesting problem not known to be contained in any smaller class. But then would SPP be natural simply because it contains graph isomorphism? On the other hand I find BPP a natural way to define probabilistic computation even though it fails this test. Does a class go from natural to unnatural if a new algorithm for a problem is found?
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.
Posted by Lance to My Computational Complexity Web Log at 10/25/2004 01:27:12 PM