News for hackers. Stuff that matters.
Re:P versus NP Explained by pdpi on Monday February 03, 2014 @09:21AM (#7170713)
The 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.

Re:P versus NP Explained by VLM on Monday February 03, 2014 @12:57PM (#7172299)
"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.

Re:P versus NP Explained by pdpi on Monday February 03, 2014 @03:05PM (#7173096)
Algorithmic 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.