One should disregard the “proof” shown in the April, 1975, issue of Scientific American. IIRC, the Mathematical Games column in that issue listed several, recent mathematical breakthroughs. They were all hoaxes. It was, after all, the April issue.
Beruang: Your demonstration fails as a proof because it addresses only local elements of a global scheme. Say you color region A as you suggest. Consider region B, which is contiguous to some regions(s) contiguous to region A. You don’t have the freedom to color B as you did A since some color(s) have already been determined. Any proof must show that those colors ‘forced’ on region B can be accomodated in a 4-color scheme, and that’s where your demonstration falls short.
RM you need six colors for your example, don’t leave out the water, it counts as a region on the map.
Let me throw my hat into the ring maligning the teaching abilities of Dr. Haken. He really sucked, and he wasn’t the most forgiving or willing to put in time away from class. The soap issue didn’t really inspire many to seek out of class help either, a theme in the math depertment. What fun!
I don’t know how the super computer jocks did it, but a few minutes of screwing around in Corel Draw produced a seven region map that requires five colors. Region 1 is central and is bordered by Regions 2, 3, 4, 5, 6 & 7. Region 2 is bordered by 1, 3 & 6. R3 is bordered by 1, 2, 4 & 6. R4 is bordered by 1, 3, 5 & 6. R5 is bordered by 1, 4, 6 & 7. R6 is bordered by 1, 2, 3, 4, 5 & 7. R7 is bordered by 1, 5, 6 & 7.
I can’t put it up anywhere on the Web, but I’ll be glad to e-mail anyone a bitmap.
Uhh, Beatle? I thought the supercomputer jocks proved that what you have done in CorelDraw couldn’t be done (assuming the contiguous-regions-only and flat-space caveats above). So either you’re pulling our legs or the supercomputer jocks were wrong. Or else I’m very confused.
Nahh, couldn’t be. I’m NEVER confused.
I’m often more of an empiricist than a theoretician.
Okay, I sketched out the above example, and assigned four colors to the regions:
Region 1 is blue
Regions 2, 4 and 7 are yellow
Regions 3 and 5 are orange
Region 6 is red.
I feel much better now.
Yeah, that works with four. Ah, well…nice thing about the empirical approach is that you aren’t often dismayed by early failures. Maybe it will take 110 regions. I’ll continue to hack at it.
That sounds simpler than NP-complete, unless there is an additional restriction on maximum number of parallel tasks.
John W. Kennedy
“Compact is becoming contract; man only earns and pays.”
– Charles Williams
Knapsack: a burglar can only fit so much stuff in his bag. What objects should he take?
Side note: although the generalized Knapsack problem is NP-complete, there has been some progress in solutions. Trapdoor ciphers based on the Knapsack problem have been broken as long ago as 1984. See Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir’s signature scheme, The rise and fall of knapsack cryptosystems, Practical Attack against Knapsack based Hash Functions, [url=http://www.mi.informatik.uni-frankfurt.de/research/papers/ritter.knapsack_cryptosystems.1996.psBreaking Knapsack Cryptosystems by Max-Norm Enumeration.
This is my first attempt at UBB code, hope I don’t screw up …
jrf
Rats.
jrf
I have 2 bitmaps from a ‘Macalaster College Problem of the Week’, which was a slightly modified version of Martin Gardner’s 4/75 April Fools column. The author of the Problem of the Week was Stan Wagon, archived by J. Erickson, but unfortunately I can no longer access this site & my search engine can’t find it.
One of the bitmaps is 4-colored, the other blank. E-mail me if you want one or both.
Wagon gave a hint on solving this, based on Kempe chains (named after an early ‘prover’ of the theorem). Say the colors are red, yellow, blue & green, and you’ve partially 4-colored the map. Pair the colors, thinking of red/yellow islands within blue/green seas (with lakes possible, and islands within lakes, etc.) You have red/yellow and blue/green Kempe chains.
If you run into a jam, you can reverse the coloring within a Kempe chain touching the problem spot (i.e., red becomes yellow & vice versa). Proving that this always works is extremely hard, but in practice, it’s pretty easy.
JonF, thanks for the knapsack links. I’ll be sure to check them out.
I think JWK is right. The longest path problem assumes that you have a fixed number of resources to throw at the tasks.
The “attack” on the knapsack problem is interesting. I wonder if it could be used to “attack” the other NP complete problems as well? If I remember right, the heuristic partial solutions weren’t universal, the way a true solution would be.