4 ms·
Three minor editorial comments: 1) Its not "most real-world challenges" its more like "some easily explainable problems which don't scale very well". Most rea
by VLM 13y ago
Three minor editorial comments:
1) Its not "most real-world challenges" its more like "some easily explainable problems which don't scale very well". Most real world challenges are simple P problems or NP problems on a very small scale. Sample the angular position of all four wheels a thousand times per second, calculate the apparent angular acceleration, cross check with the other wheels, and if its ridiculous, modulate the brakes a hundred times per second. Even if that problem wouldn't scale to 5000 wheeled vehicles, that simply doesn't matter to our 4 wheeled cars, or even 18 wheel semi trucks. Or TLDR most real world problems are either P or small enough scale NP not to matter.
2) "computers being able to quickly solve problems" More like anything being able to solve problems. Classic computer limits are FP multiplier speed, memory limits, stuff like that. This is a problem solving limitation inherent to the class of problem, not a computer technology limitation. A classic Searle Chinese Room emulating a processor, or a single human brain, is just as limited by NP problem solving limitations. Or something along the lines of this problem will not be solved by making a better computer.
3) "Unfortunately, many with computer science degrees" rewrite to "Unfortunately, many computer science degree programs don't require a class in automata theory..."
Please don't overestimate three minor editorial comments; it is a good introductory article.
- cousin_it 13y ago> most real world problems are either P or small enough scale NP not to matter. Isn't that a kind of self-fulfilling prophecy? If we had an efficient way to solve NP-complete problems, they'd be more widely used in the real world.
- pdpi 13y agoThe article describes P vs NP as the difference between decision/optimisation problems, which doesn't make it seem like what sort of machine you use to solve them has much to do with it at all. You can also think of it in terms of those problems that can be solved in poly time, either by deterministic (P) or non-deterministic (NP) Turing machines. From that perspective, the fact that you're using a modern computer, which is effectively a deterministic Turing machine, matters a whole lot.
- VLM 13y ago"the fact that you're using a modern computer ... matters a whole lot" I'd disagree in that its a math / logic problem not a computer problem. Most of the applications seem to involve a computer or its assumed that if a solution is found it would be applied by computers. The Pythagorean theorem does not care if its written with chalk or dry erase markers. In a similar way most automata theory proofs don't use or rely upon a computer other than in the word processor and wiki browser sense. Or maybe another way to say it is the guys who make computers faster at great effort and expense will never make NP problems P just by making faster transistors or putting more transistors on a single die. The whole topic is not really a computer problems.
- pdpi 13y agoAlgorithmic complexity is predicated on what sort of computational model you're working on top of. For the most part, that means "Deterministic Turing Machines", but that's not the only sort of computing machine out there. E.g. quantum computers can solve a whole class of NP problems (like factorisation) in poly time.