This post explain nothing.
Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaningless.
Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaningless.
But for coders who've never seen problem classification theory before (not Big O notation), the subject can appear opaque and irrelevant. I'm all for simplified introductions that help those less familiar with formal computer science become more aware of the theoretical side.
I'll give it a shot.
Let me tell you about an onion. One interesting CS topic to google for is Chomsky Hierarchy. You can start out with really simple grammars (rules) and languages (what the rules result in) and advance toward more complicated problems. Amazingly, for no apparent reason, each step contains everything smaller than the step below plus some set of new things that end up equivalent to each other, even if it takes lots of effort to prove it. Like layers on an onion. For example, its mathematically impossible to come up with a math-type regex that can't be solved by a NFA and impossible to come up with a NFA that can't be solved by a DFA, and all those equivalent regular languages live inside a bigger class of CFLs and PDAs and so on, bigger and more complex every stage you go up. Its all very complicated and highly developed and pretty much figured out at the lower and mid levels. Turing machines seem to be the king of the hill at the somewhat mysterious top. So, thats enough talk about the shape on an onion.
Deep in the onion, there exists one terribly complicated set of vaguely equivalent problems that Turing machines can solve, which scale horribly as the size of the problem increases. And then there is a competing set of problems that scale really easily and are quickly solved. Inside the families they are all cousins of each other and never marry outside their families, ever. So if you find a way to quickly solve one NP its been proven you can warp that technique into solving another NP problem, more or less. But it never, ever, so far, hops between families. NP problems and P problems just don't procreate together, sorta. Its just like when you slice open an onion and find two independent sprouts that have nothing to do with each other. Why, I donno. Nobody knows why. At least WRT P=NP, donno about the onions.
Now its time for idle speculation. How do these apparently separate families fit in the Chomsky Hierarchy, could there be another separate layer of NP problems above the P problems and a matching layer of NP "machines" vs P "turing machines"? Is there a layer on top where if you take a turing machine and add magic pixie dust now it can solve NP problems in P time? If P=NP so this disjoint set of problems is just equivalent Turing solvable problems, how come nobody has proven it yet despite enormous effort and motivation? How come languages that apparently have nothing to do with each other like REGEX and DFA are mathematically proven the same but nobodies proven it yet for P = NP, doesn't that imply its incredibly unlikely they are the same because all the other levels "intermingle" their languages with each other? How does quantum computing fit in, if it does at all in any way?
I tried hard to shove P=NP and the Chomsky hierarchy together, its not going to be insightful to point out that I really swung a sledgehammer to slam this connector into that socket; I already know that. Also I simplified some stuff (well, OK, I simplified everything). But its hopefully an entertaining read and not entirely irrelevant and opaque.
You just proved the point. I'm going to read what you wrote, but most people will not.
The point of my resource was to approachable and consumable within seconds.
None the less, in the spirit of XKCDs "Up Goer Five" I present:
The Crying Onion of P probably does not equal NP.
Computer innards are layered like onions. Just like an onion, bigger computer innard layers contain all of the smaller less complicated layers inside them. There are lots of layers, some much better understood than others. Everything in one layer is the same as everything else in its layer even if at first glance it looks very different. One possible exception is the most difficult layer of the computer innard onion might be split into two layers P and NP. Smart people have worked very hard for many years but are not sure if the layers are split or not. The onion of P probably does not equal NP is so complicated it makes people cry, just like an onion.
And in the proud tradition of the previously mentioned XKCD comic, "Lots of fire comes out here"
Some things aren't consumable in seconds. You either put in the effort to learn something properly, or you don't and content yourself with not knowing.
If you dive super deep you don't have a summary in plain language, you have a competing explanation.
There are already a million of those; this isn't that.
Now imagine you're speaking to someone who read this post. That person is just as ignorant as our big-mouthed friend, but they don't even know it. They read some post, learn a new term or two, and go out into the world not knowing that what they just read contains no real knowledge whatsoever. A post like this does a huge disservice to that person, because not only does it leads them into ignorance, it actually makes them less empowered to rise above it.
As expected from HN, upvotes and front page :D!