tag:blogger.com,1999:blog-3722233.post6576209065051505306..comments2023-02-08T10:05:26.048-06:00Comments on Computational Complexity: What is a natural question? Who should decide?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3722233.post-71320851358074003782021-06-02T23:51:04.953-05:002021-06-02T23:51:04.953-05:00Reminds me of my experience with the unsolvability...Reminds me of my experience with the unsolvability of the quintic: I wanted to know why the quintic could not be solved, and one of the algebra textbooks I looked at did Galois theory but regarded the unsolvability of the quintic as a mere curiosity (and hence it was relegated to an exercise) compared to the awesomeness of the Galois correspondence between groups and fields. I call bullshit on that!- the Quintic is WHY we care about the Galois Correspondence!gasarchhttps://www.blogger.com/profile/03004932739846901628noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-44355831690107170582021-06-02T19:09:16.098-05:002021-06-02T19:09:16.098-05:00I would say that there are two different senses of...I would say that there are two different senses of the word "natural." What might seem natural to a person *asking* questions won't necessarily coincide with what seems natural to a person who is developing the technology to *answer* questions. I would not call your question about Hilbert's Tenth Problem "the wrong question"; it's just that you should not be surprised if the people who actively try to answer these questions slice and dice the space in a completely different way.<br /><br />Here's a possible analogy from computer science. A practitioner might want to know what problems can be solved with 100 terabytes of memory and 1000 hours of computer time. A theorist might find those constraints "unnatural" compared to the question of what problems can be solved in polynomial time or polynomial space. Both perspectives are valid in their proper contexts.<br /><br />This discussion reminds me of something that happened when the proof of Fermat's Last Theorem hit the headlines. Some non-mathematicians wondered out loud why mathematicians would care about such a theorem. Some number theorists reacted by saying, "Well, we don't actually care about Fermat's Last Theorem. That would be silly. What we actually care about is that the semistable Shimura-Taniyama-Weil conjecture has been proved. Now *that's* interesting!" Even though I am a mathematician with some interest in number theory, I found this reaction to be disingenuous. There is no way that people would have been so interested in the semistable case of the Shimura-Taniyama-Weil conjecture if it had not already been shown to imply Fermat's Last Theorem. In fact, I seriously doubt that Wiles himself would have worked as hard as he did on it if there had been no connection to Fermat's Last Theorem. Just because a question is not "natural" in the sense of occupying a central position from the point of view of someone trying to build machinery doesn't mean that it isn't interesting and natural in another sense. To deny this strikes me as some kind of weird snobbery, or at least a narrow view of what the mathematical enterprise is about.Timothy Chowhttps://www.blogger.com/profile/15157353087847193176noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-23150495384580241662021-05-30T21:33:44.017-05:002021-05-30T21:33:44.017-05:00I think a lot of naturalness has to do with robust...I think a lot of naturalness has to do with robustness. E.g. P vs NP is "natural" because P and NP are largely machine-independent. Problems about AC0 are natural because AC0 has many representations (circuits, logic, alternating TM). Problems about LINTIME are less "natural" because they get stuck in the weeds of specific constructs. So maybe questions about Diophantine equations are "natural" if equations of the given degree/have many interpretations.<br /><br />Alternatively, I think if a layperson is truly invested in the answer to a math problem, then it is because it arises as the product of some natural process (e.g. physics, chemistry, biology, optimization of a real-world process). So the questions we care about would ideally be natural by definition. But maybe there's a distinction between physical naturalness and mathematical naturalness.Anonymousnoreply@blogger.com