Hacker News Reader

I have been convinced that P==NP since my first exposure to the topic in university. There are NP complete problems where I can really not imagine how they could be solved quickly, but vertex three coloring just looks so doable to me by some informal intuitive arguments. In another life I would devote my life to fleshing out the argument and proving P==NP. Or at least learn where my intuitive argument fails.

View on HN

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.

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.

Reply on news.ycombinator.com