Once you know something can be done, doing it is much easier


Unfortunately, I don't remember the name of the star of this story, but I'm told that there was a notable mathematician who believed the Perfect Graph Conjecture to be false and spent many years trying to prove it one way or another.

Meanwhile, another mathematician (presumably László Lovász) announced that he had found a proof (in the affirmative).

Upon hearing the news that the open question had been resolved, the first mathematician was able to produce a proof within 90 minutes.

Once again showing that it's much easier to do something once you know it can be done.

Comments (22)
  1. pcooper says:

    Interesting story, and I'm sure there are plenty of other examples.

    The word "notable" in my browser was hyphenated no-table, which took me a bit of reparsing to figure out what it was trying to say. I'm no grammar expert, but I would have expected "not-able". Looks like the auto-soft-hyphen script isn't perfect, or my expectations are wrong.

  2. Chris B says:

    It seems fairly natural that proving a falsehood would be more likely to end in failure than proving truth.

  3. Mijzelf says:

    @Chris B

    Why? To prove a falsehood you'll only have to come up with 1 example that doesn't match the theory. To prove truth you'll have to prove such an example cannot exist.

  4. Mike says:

    Reminds me of 8th grade. Starting with the speed of light is fixed and deriving special relativity. Doesn't make me Einstein but knowing it could be done by simple geometry made it easy enough for an 8th grader.

  5. Joshua Ganes says:

    @Chris B – I'm not so sure that proving a falsehood is more likely. There are many straightforward proofs where assuming premise A leads to an obvious logical contradiction. This proves that A is false. There are also many proofs by counterexample, where a single case that contradicts a premise can be found.

    I've always been curious if there was a general way to classify problems into easy or hard to solve and what type of approach would be more effective in coming up with a proof.

  6. Joshua says:

    Sometimes the solution comes from asking "How can the other guy know it?"

  7. Maurits says:

    Claude Berge, perhaps?

  8. JJJ says:

    In an assembly language class I took in college, assignments were graded by the size of the code in bytes (well, correctness counted too).  Some years, the instructor would tell the size of his solution when handing out the assignment, and some years he'd wait until after.  In the former case, the top students would consistently match or beat theA size of his solution.  In the latter, the top students often would produce significantly larger solutions.  Pretty amazing how knowing a better solution exists opens the path to finding it.

    (And of course if a student beat the instructor's code size, that solution would become the instructor's solution, making it considerably harder to beat in later years.  But yet it would happen when the code size was announced beforehand.)

  9. Clodney says:

    This same phenomenon also applies to patents – oftentimes a novel invention is completely obvious once described.  This seems to fuel some of the patent rage out there.

  10. Maurits says:

    Hyphenating "notable" is tricky.

    The etymological school would have you hyphenate it "not-able" since it derives from "note". But "not-able" looks a lot like "not able" and the notable mathematician in question might take objection.

    The phonetic school would have you hyphenate it "no-ta-ble" which resulted in the "no-table" hyphenation.

    My question is, why is it being hyphenated at all? I would expect hyphenation to prefer sending "notable" down to the next line in its entirety since hyphenating it only extends the line by three characters, and we're dealing with fairly long lines anyway.

  11. Clodney, what I've noticed is that while a solution is often obvious to an engineer in the field, the question isn't.

  12. Jim Howard says:

    The four minute mile was considered to unattainable, until Roger Banister ran a mile in four minutes.  After that, everyone and his brother could do it.  This is seminal case.

  13. JM says:

    "I've always been curious if there was a general way to classify problems into easy or hard to solve and what type of approach would be more effective in coming up with a proof."

    In its most general form, the answer to your question is "no". That runs afoul of various incompleteness theorems. However, the less formal notion of what is complex and what is simple, and whether we can distinguish between the two and how, is probably one of the deepest issues in mathematics — and computer science, for that matter.

  14. Matt says:

    Interestingly the reverse is also true:

    Once you know something can't be done, not doing it is much easier.

  15. Chris B says:

    My attempt at humor obviously failed…

    I did not mean that proving a claim to be false is more difficult than proving one true. I meant that proving a false claim to be true (or vice versa), as our original mathematician was attempting, will be more difficult (impossible) than proving a true statement true (or false statement false).

  16. Chris B says:

    My attempt at humor obviously failed…

    I did not mean that proving a claim to be false is more difficult than proving one true. I meant that proving a false claim to be true (or vice versa), as our original mathematician was doing, will be more difficult (impossible) than proving a true statement true (or false statement false).

    (Sorry if I double post, I think I timed out while writing that…)

  17. Kevin says:

    @Maurits: Why not just do "nota-ble"?

  18. Maurits says:

    @Kevin: no syntactic ambiguity with "nota-ble"; it's fine (assuming you are tolerant of the phonetic school.)

    There's a visual payoff you get from adding hyphens which varies depending on how much whitespace you avoid (either at the end of the line, or between words if you're justifying.) There's also a visual penalty you get from adding hyphens because the reader has to glue the pieces of the word back together in their head.

    I posit that soft hyphens should only be added when the payoff is greater than the penalty. For example, if you're reading a newspaper with three-inch-wide columns, and someone uses a three words in a row that are two inches long, hyphenating the word in the middle has a high payoff and a low penalty.

    I further posit that when hyphenating a short word on a blog with wide columns, the payoff is low and the penalty is high.

    [I agree that some browsers are way too aggressive with hyphens, but there does not appear to be a way to tune the algorithm. -Raymond]
  19. Dimiter 'malkia' Stanev says:

    Is that how placebo works? Homeopathy? lol….

  20. Ian Boyd says:

    A developer thought his code was bug-free, and spent many hours trying to find a bug – without success. After release, there came back word that a customer was experiencing a bug in the developers code.

    Upon hearing the news the developer was able to reproduce and correct the bug within 45 minutes.

  21. Neil says:

    Presumably if he originally thought that it was false, he was more interested in disproving it, and didn't really have the heart to try to prove it?

  22. Joker_vD says:

    @Maurits: How am I glad my language has strict and fixed rules on hyphenating words… it would be "no-tab-le", invariably. Oh well, English is not well known for having its punctuation rules written out somewhere and being agreed upon.

Comments are closed.