[Videege]

So that's the question. Does P=NP? Not that the matter is exactly one of opinion, but the general consensus is of course no.
Perhaps a better topic for discussion is how (relatively) new computational complexity classes, like BQP (Bounded-error, quantum, polynomial time - for quantum computers), fall in the complexity spectrum. What are the implications of the answers to each of these question for computer science as we know it?

How are we going to cope with the new complexity classes, like BQP, which holds the key to cracking all modern encryption techniques (granted, we'll need a fully operational battlestation quantum computer to do so, but they're coming)?

What do you guys think?

This post has been edited by Videege: 10 December 2007 - 12:41 PM

[William_Wilson]

I just finished my algorithms exam and that stupid question was on there... he didn't really want a thought out explanation just regurgitation from our text book. Personally I think the day is coming where P will in fact equal NP. I don't think the type of algorithms are going to change, but rather a better storage device or more dynamic locations and lookup will allow more and smaller variables to come into play, which might actually bend the rules of what polynomial time really is..

if it doesn't run in polynomial time, but we can bound it by n^n is that good enough? For large sets of data it would take loads of time, but it's polynomial...

I've seen where universities are offering cash prizes of up to a million dollars for someone to prove that P = NP or P != NP, so I imagine there will be no quick end to this debate.