Suppose someone offered you a bet on P = NP. How should you go about deciding whether or not to take it?
Does it make sense to assign probabilities to unproved mathematical conjectures? If so, what is the probability of P = NP? How should we compute this probability, given what we know so far about the problem? If the answer is no, what is a rational way to deal with mathematical uncertainty?
Scott Aaronson and many others in his field have essentially bet their careers that P ≠ NP (at least, I think the whole hierarchy of complexity classes would collapse if P = NP), while only a bunch of cranks (so far as I’ve heard) have bet a substantial amount of their life’s efforts on P = NP. That’s as good a statement of betting odds as any.
As for whether it’s legitimate to do so, well, that’s Bayesian probability for you. You’ve got to have some way of dealing with subjective uncertainty, and you get better results in the long run if your method of dealing with it is like unto the laws of probability.
Let’s say you’re the first person to work on P = NP. What then? (Assume that you have enough mathematical ability to produce most of the results on it that we have so far.)
Well, I’m pretty sure that the smart money is all on one side of the question because of certain heuristic evidence that becomes very clear when you’ve worked with these complexity classes for a long while.
It’s the same reason the smart money was on Fermat’s Last Theorem being true (prior to the proof being found); not only would it have been very unusual in mathematics for this simple Diophantine equation to have its first nontrivial solution only when the numbers became absurdly large, but it is equivalent to a beautiful conjecture in elliptic curves which seemed to admit of no counterexamples.
There’s plenty of inductive evidence found and used in the actual doing of mathematics; it just doesn’t make the textbooks (since you generally don’t publish on a subject unless you’ve found a proof, at which point the inductive evidence is utterly redundant). Yet it guides the intuition of all mathematicians when they decide what to try proving next.
Suppose you test Fermat’s Last Theorem for n up to 10^10, and don’t find a counterexample. How much evidence does that give you for FLT being true? In other words, how do you compute P(a counterexample exists with n<=10^10 | FLT is false), since that’s what’s needed to do a Bayesian update with this inductive evidence? (Assume this is before the proof was found.)
I don’t dispute that mathematicians do seem to reason in ways that are similar to using probabilities, but I’d like to know where these “probabilities” are coming from and whether the reasoning process really is isomorphic to probability theory. What you call “heuristic” and “intuition” are the results of computations being done by the brains of mathematicians, and it would be nice to know what the algorithms are (or should be), but we don’t have them even in an idealized form.
The most influential books on the topic I know of are Mathematics and Plausible Reasoning Volume I: Induction and Analogy in Mathematics, and Mathematics and Plausible Reasoning Volume II: Patterns of Plausible Reasoning (amazon link) by George Pólya.
There’s a difficulty here involving the fact that every finite set of possible counterexamples has measure zero in the set {(a, b, c, n) | a, b, c, n in N} equipped with the probability measure that assigns each possible counterexample an equal probability.
So all the usual biases and cognitive gotchas involving probability and infinity come into play (even when the people doing the thinking are mathematicians!), and all bets are off.
My hypothesis is that the commonly used prior for counterexample distributions is exponential. As the lower bound K >= a, b, c, n on possible counterexamples increases, the exponential is updated into something close to uniform on the rest of {(a, b, c, n) | a, b, c, n in N}.
This does somewhat dodge the question, but it does make a difference that an infinite set of counterexamples can be associated with each counterexample. That is, if (a,b,c,n) is not a solution to the Fermat equation, then (ka,kb,kc,n) isn’t either for any positive integer k.
If you’re thinking of this, you’re
misremembering—that bet (of $200,000) was that Vinay Deolalikar’s recent P
!= NP paper would not win the Clay Millenium prize. (In the comments,
Aaronson says
“P≠NP is exactly the ‘expected’ answer!”;
the bet was his way of keeping people from accusing him of rushing to judgment
when he said that he didn’t think the paper would turn out to successfully
prove that expected answer even though he hadn’t read the whole thing.)
Ah, you’re entirely right. I didn’t misremember—I read his blog rather religiously. I just apparently wasn’t quite awake when I wrote what he was betting on.
I should also clarify that he didn’t have anyone matching even a lesser amount in the case that the paper was indeed unsuccessful (which it appears to be as it stands, but Aaronson’s bet gives it a while to correct problems). His goal, which didn’t exactly work, was to get people to stop asking him about the paper. I say it didn’t work, because he probably got even more people commenting on the bet, and still a large number asking about the paper.
Here are some papers I found recently that seem to represent the state of the art on the issue of how to deal with uncertainty in mathematics. None of them really get very far beyond “let’s try to apply probability theory”, but at least the problem is not being completely ignored by mathematicians and philosophers.
Bayesianism in mathematics, a book chapter in Towards a Philosophy of Real Mathematics by David Corfield
One could say that most of math is already about uncertainty: when you have a system and ways of refining it, it is in a way a form of applying knowledge to resolve uncertainty. For example, applying a function to a parameter, or combining morphisms. A lot of analysis is about approximation or representing systems that expect future observations. It is a very narrow sense of “dealing with uncertainty” that would require going to the fringe.
I don’t understand the point of your comment. It should have been clear from the context that by “dealing with uncertainty in mathematics” I did not mean things like proving or disproving a conjecture, thus resolving its uncertainty, but rather how to make bets involving mathematical statements that we don’t know how to either prove or disprove. Are you saying that the latter is not an important problem, or just that you don’t like that I’m using the phrase “dealing with uncertainty in mathematics” to refer to it?
You don’t have to resolve all of uncertainty in one go. For example, you could restrict a function to part of a domain, thus deciding that it is only this part that you are interested in, instead of the whole thing.
What you seem to mean is non-rigorous methods for making uncertain conclusions about mathematical structures. It is about dealing with uncertainty about mathematics on non-mathematical level of rigor. Correct?
Yes, something like that, except that “non-rigorous” seems too prejudicial. Why not just “methods for making uncertain conclusions about mathematical structures”, or “dealing with uncertainty about mathematics”?
Suppose someone offered you a bet on P = NP. How should you go about deciding whether or not to take it?
Does it make sense to assign probabilities to unproved mathematical conjectures? If so, what is the probability of P = NP? How should we compute this probability, given what we know so far about the problem? If the answer is no, what is a rational way to deal with mathematical uncertainty?
It only took 7 years to make substantial progress on this problem: Logical Induction by Garrabrant et al..
Scott Aaronson and many others in his field have essentially bet their careers that P ≠ NP (at least, I think the whole hierarchy of complexity classes would collapse if P = NP), while only a bunch of cranks (so far as I’ve heard) have bet a substantial amount of their life’s efforts on P = NP. That’s as good a statement of betting odds as any.
As for whether it’s legitimate to do so, well, that’s Bayesian probability for you. You’ve got to have some way of dealing with subjective uncertainty, and you get better results in the long run if your method of dealing with it is like unto the laws of probability.
Let’s say you’re the first person to work on P = NP. What then? (Assume that you have enough mathematical ability to produce most of the results on it that we have so far.)
Well, I’m pretty sure that the smart money is all on one side of the question because of certain heuristic evidence that becomes very clear when you’ve worked with these complexity classes for a long while.
It’s the same reason the smart money was on Fermat’s Last Theorem being true (prior to the proof being found); not only would it have been very unusual in mathematics for this simple Diophantine equation to have its first nontrivial solution only when the numbers became absurdly large, but it is equivalent to a beautiful conjecture in elliptic curves which seemed to admit of no counterexamples.
There’s plenty of inductive evidence found and used in the actual doing of mathematics; it just doesn’t make the textbooks (since you generally don’t publish on a subject unless you’ve found a proof, at which point the inductive evidence is utterly redundant). Yet it guides the intuition of all mathematicians when they decide what to try proving next.
Compare Einstein’s Arrogance.
Suppose you test Fermat’s Last Theorem for n up to 10^10, and don’t find a counterexample. How much evidence does that give you for FLT being true? In other words, how do you compute P(a counterexample exists with n<=10^10 | FLT is false), since that’s what’s needed to do a Bayesian update with this inductive evidence? (Assume this is before the proof was found.)
I don’t dispute that mathematicians do seem to reason in ways that are similar to using probabilities, but I’d like to know where these “probabilities” are coming from and whether the reasoning process really is isomorphic to probability theory. What you call “heuristic” and “intuition” are the results of computations being done by the brains of mathematicians, and it would be nice to know what the algorithms are (or should be), but we don’t have them even in an idealized form.
The most influential books on the topic I know of are Mathematics and Plausible Reasoning Volume I: Induction and Analogy in Mathematics, and Mathematics and Plausible Reasoning Volume II: Patterns of Plausible Reasoning (amazon link) by George Pólya.
There’s a difficulty here involving the fact that every finite set of possible counterexamples has measure zero in the set {(a, b, c, n) | a, b, c, n in N} equipped with the probability measure that assigns each possible counterexample an equal probability.
So all the usual biases and cognitive gotchas involving probability and infinity come into play (even when the people doing the thinking are mathematicians!), and all bets are off.
My hypothesis is that the commonly used prior for counterexample distributions is exponential. As the lower bound K >= a, b, c, n on possible counterexamples increases, the exponential is updated into something close to uniform on the rest of {(a, b, c, n) | a, b, c, n in N}.
This does somewhat dodge the question, but it does make a difference that an infinite set of counterexamples can be associated with each counterexample. That is, if (a,b,c,n) is not a solution to the Fermat equation, then (ka,kb,kc,n) isn’t either for any positive integer k.
And, mid-2010, Scott Aaronson also literally put down a large bet that P != NP.
If you’re thinking of this, you’re misremembering—that bet (of $200,000) was that Vinay Deolalikar’s recent P != NP paper would not win the Clay Millenium prize. (In the comments, Aaronson says “P≠NP is exactly the ‘expected’ answer!”; the bet was his way of keeping people from accusing him of rushing to judgment when he said that he didn’t think the paper would turn out to successfully prove that expected answer even though he hadn’t read the whole thing.)
Ah, you’re entirely right. I didn’t misremember—I read his blog rather religiously. I just apparently wasn’t quite awake when I wrote what he was betting on.
I should also clarify that he didn’t have anyone matching even a lesser amount in the case that the paper was indeed unsuccessful (which it appears to be as it stands, but Aaronson’s bet gives it a while to correct problems). His goal, which didn’t exactly work, was to get people to stop asking him about the paper. I say it didn’t work, because he probably got even more people commenting on the bet, and still a large number asking about the paper.
Here are some papers I found recently that seem to represent the state of the art on the issue of how to deal with uncertainty in mathematics. None of them really get very far beyond “let’s try to apply probability theory”, but at least the problem is not being completely ignored by mathematicians and philosophers.
Bayesianism in mathematics, a book chapter in Towards a Philosophy of Real Mathematics by David Corfield
Non-deductive Logic in Mathematics, by James Franklin
Bayesian Networks for Logical Reasoning, by Jon Williamson
One could say that most of math is already about uncertainty: when you have a system and ways of refining it, it is in a way a form of applying knowledge to resolve uncertainty. For example, applying a function to a parameter, or combining morphisms. A lot of analysis is about approximation or representing systems that expect future observations. It is a very narrow sense of “dealing with uncertainty” that would require going to the fringe.
I don’t understand the point of your comment. It should have been clear from the context that by “dealing with uncertainty in mathematics” I did not mean things like proving or disproving a conjecture, thus resolving its uncertainty, but rather how to make bets involving mathematical statements that we don’t know how to either prove or disprove. Are you saying that the latter is not an important problem, or just that you don’t like that I’m using the phrase “dealing with uncertainty in mathematics” to refer to it?
You don’t have to resolve all of uncertainty in one go. For example, you could restrict a function to part of a domain, thus deciding that it is only this part that you are interested in, instead of the whole thing.
What you seem to mean is non-rigorous methods for making uncertain conclusions about mathematical structures. It is about dealing with uncertainty about mathematics on non-mathematical level of rigor. Correct?
Yes, something like that, except that “non-rigorous” seems too prejudicial. Why not just “methods for making uncertain conclusions about mathematical structures”, or “dealing with uncertainty about mathematics”?
(Retracted; useless speculation.)