[artosispylon]

By definition, each NP-complete problem is provably as hard as another though. Graph coloring can be reduced in polynomial time to every NP-C problem. It doesn't really make sense to me that one problem can just "look so doable" when they're really just the same problems.

[danbruc]

They are of course all reducible to each other but that doesn't necessarily mean that they are all equally hard to attack. That's very common in mathematics where reformulating the problem can make the relevant bits and pieces more obvious while the original formulations obfuscated them. In the same way some NP-complete problems look harder to me because they seem to require global information while vertex three coloring looks to me like it should be solvable with quite localized information. Another good analogy is probably the way switching between position and momentum eigenstates in quantum physics makes different problems easier to express and handle.