Proverbs, aphorisms, quotations (English) | by Linux fortune |
At about 2500 A.D., humankind discovers a computer problem that *must* be solved. The only difficulty is that the problem is NP complete and will take thousands of years even with the latest optical biologic technology available. The best computer scientists sit down to think up some solution. In great dismay, one of the C.S. people tells her husband about it. There is only one solution, he says. Remember physics 103, Modern Physics, general relativity and all. She replies, "What does that have to do with solving a computer problem?" "Remember the twin paradox?" After a few minutes, she says, "I could put the computer on a very fast machine and the computer would have just a few minutes to calculate but that is the exact opposite of what we want... Of course! Leave the computer here, and accelerate the earth!" The problem was so important that they did exactly that. When the earth came back, they were presented with the answer: IEH032 Error in JOB Control Card. | |
The algorithm for finding the longest path in a graph is NP-complete. For you systems people, that means it's *real slow*. -- Bart Miller | |
HOW TO PROVE IT, PART 3 proof by obfuscation: A long plotless sequence of true and/or meaningless syntactically related statements. proof by wishful citation: The author cites the negation, converse, or generalization of a theorem from the literature to support his claims. proof by funding: How could three different government agencies be wrong? proof by eminent authority: 'I saw Karp in the elevator and he said it was probably NP- complete.' | |
HOW TO PROVE IT, PART 4 proof by personal communication: 'Eight-dimensional colored cycle stripping is NP-complete [Karp, personal communication].' proof by reduction to the wrong problem: 'To see that infinite-dimensional colored cycle stripping is decidable, we reduce it to the halting problem.' proof by reference to inaccessible literature: The author cites a simple corollary of a theorem to be found in a privately circulated memoir of the Slovenian Philological Society, 1883. proof by importance: A large body of useful consequences all follow from the proposition in question. |