When Less Is More
Claiming less may be a good idea
Robert Browning was an English poet of world renown in the Victorian age. His fame rests mostly on his dramatic monologues, in which characters reveal indirectly much about themselves. Here you can actually listen to a recording made in 1889 of him trying to read from his poem “How They Brought the Good News from Ghent to Aix,” which was one of Ken’s father’s favorites. After Browning’s passing on 12/12 of that year, this was said to have been the first recording preserving the voice of a deceased person.
Today I want to talk about claims of proofs that would resolve the vs question, and may reveal more about the provers than about the problem. I also would like to make a modest suggestion.
The phrase “less is more” is first found in print in Browning’s poem “Andrea del Sarto” in 1855:
Who strive – you don’t know how the others strive
To paint a little thing like that you smeared
Carelessly passing with your robes afloat,-
Yet do much less, so much less, Someone says,
(I know his name, no matter) – so much less!
Well, less is more, Lucrezia.
Right now there are a slew of papers that are circulating that have proofs that . Currently we have fewer papers that claim to prove that they are unequal. Historically, of 96 proof claims logged on Gerhard Woeginger’s P versus NP page, exactly half are for “equal,” with the other 48 divided into 42 for “not equal” (plus a variant on one of the “equal” claims) and a handful for “undecidable/other.”
The Tilt Toward Equal
The near-parity of the numbers is striking. Ken and I see two factors at work. One is “demand-side”: philosophically many people accept the position that being able to verify a needle in a haystack does not confer the ability to find it, and this is reflected in “not equal” out-pointing “equal” by 126–12 in Bill Gasarch’s latest poll of experts. In a SlashDot poll open to the general public, the current status is approximately 5,000 for “equal,” 10,000 for “not equal,” and almost another 10,000 for “undecidable.” The demand-side favors “not equal.”
The other is “supply-side”: to show “equal” one “only” needs to present an algorithm that one claims can solve some particular -complete problem. To claim that they are unequal you need to claim to prove that there is a lower bound. Since we really have no idea how one would even start a proof that there is no algorithm at all for some problem like SAT, the lower bound claims are harder to make. The logical sentence expressing begins with an existential () quantifier, and existentials feel more appealing for the human mind to try to carry out.
As I have described many times before, the typical equality claim goes like this: One picks a favorite complete problem, reduces its solution to some powerful subroutine, and bingo we have a “proof.” Often, but not always, the subroutine is linear programming, sometimes it is convex programming. I once had a FOCS submission to review that reduced the complete problem to the shortest path problem.
The End Of the World?
Since I am writing this we have dodged the first hurdle of danger: 12/12/12 at 12:12.12 pm. It was not empty numerology: a sizable asteroid passed between earth and the Moon two minutes before that time in New Delhi. Of course the really big day 12/21/12 is looming, and Ken and I plan to discuss that soon. Our plan is to get that discussion out well before the end-of-days day. If things really do end then, well we have had fun with GLL and it would be our last chance to comment. So we plan to make the most of it.
A Modest Suggestion
My suggestion is to the claimers of big proofs like . Claim less. Really. Remember “less is more.” Here is a guide as a list:
Rather than claim , show that or has an algorithm that runs in time better than say . This would be great, would be a breakthrough, and might be read by more people. It still would be a great result.
Rather than claim , note the , show that logspace is not equal to . I would be greatly impressed with such a result and it would again be a breakthrough. Some of the “not-equal” claims “prove” this is more along the way. Just do this and we would be immensely impressed, and we would take the rest of your claims much more seriously.
Rather than claim that the Riemann Hypothesis is true, to bring in a problem from number theory, “just” show that there is no zero of the zeta function that has real part greater than . This would be another huge advance and would again be hailed as a result of first magnitude.
The main open problem is why do people who think they have resolved famous open problems never seem to check whether their methods can give simpler proofs of partial results? Why is always all or nothing? I wonder? Perhaps there is some basic principle at work here. What do you think?