4 ms·
"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 app
by 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.