6 ms·

This post explain nothing. Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaning

by jfasi 13y ago

This post explain nothing. Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaningless.

j2kun 13y ago
Not true. You can just use the characterization of NP in terms of certificates and deterministic verifying machines, and still get everything (except maybe the standard proof of the Karp-Lipton theorem).
- diminish 13y ago
  Watch out where you stand. Sons of Turing are a large mafia, which will immediately reduce every other computational construct into TMs and claim you didn't really add up anything :)
  - j2kun 13y ago
    Tell that to the Quantum Brotherhood. Edit: you may find the head of a cat in your bed, but only if you look and only with probability 1/2.
deleted 13y ago
[deleted]
lifebeyondfife 13y ago
From a technical standpoint I agree with you - the exact nature of P and NP problem classes should be explained. Here, the initials aren't even defined. 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.
- VLM 13y ago
  "the subject can appear opaque and irrelevant." 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.
danielrm26 13y ago
I strongly disagree. When so many people don't have any idea what the issue is, the most useful resource is something that approaches at THIS level, with links to deeper coverage. 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.
- jfasi 13y ago
  As innocent as they seem, posts like this are dishonest and dangerous. Imagine you're speaking to someone who actively namedrops papers and impressive concepts, but when you press them further it becomes clear they only skimmed the material and are just repeating these things to seem interesting. Imagine the contempt you'd feel for that person, who willingly puts on a show of intelligence and accepts respect from people who are impressed by their vocabulary, but is actually completely ignorant. 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.
almosnow 13y ago
I agree, even without resorting to T. machines you would be able to explain it much better easily. The author really just shows how naive he is about this field, and, salt that with a few cocky phrases like "... many with computer science degrees have a weak understanding of the concept—let alone those without any training on it" and you just get a terrible article. As expected from HN, upvotes and front page :D!

by jfasi 13y ago

This post explain nothing. Any article claiming to explain P vs NP without so much as mentioning nondeterministic and deterministic Turing machines is meaningless.

j2kun 13y ago

Not true. You can just use the characterization of NP in terms of certificates and deterministic verifying machines, and still get everything (except maybe the standard proof of the Karp-Lipton theorem).

diminish 13y ago
Watch out where you stand. Sons of Turing are a large mafia, which will immediately reduce every other computational construct into TMs and claim you didn't really add up anything :)
- j2kun 13y ago
  Tell that to the Quantum Brotherhood. Edit: you may find the head of a cat in your bed, but only if you look and only with probability 1/2.

deleted 13y ago

[deleted]

lifebeyondfife 13y ago

From a technical standpoint I agree with you - the exact nature of P and NP problem classes should be explained. Here, the initials aren't even defined. 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.

VLM 13y ago
"the subject can appear opaque and irrelevant." 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.

danielrm26 13y ago

I strongly disagree. When so many people don't have any idea what the issue is, the most useful resource is something that approaches at THIS level, with links to deeper coverage. 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.

jfasi 13y ago
As innocent as they seem, posts like this are dishonest and dangerous. Imagine you're speaking to someone who actively namedrops papers and impressive concepts, but when you press them further it becomes clear they only skimmed the material and are just repeating these things to seem interesting. Imagine the contempt you'd feel for that person, who willingly puts on a show of intelligence and accepts respect from people who are impressed by their vocabulary, but is actually completely ignorant. 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.

almosnow 13y ago

I agree, even without resorting to T. machines you would be able to explain it much better easily. The author really just shows how naive he is about this field, and, salt that with a few cocky phrases like "... many with computer science degrees have a weak understanding of the concept—let alone those without any training on it" and you just get a terrible article. As expected from HN, upvotes and front page :D!