Edit: removed Big O notation, since my point here is actually that the constant might be so large that you'd never get to a point where the limiting case would matter. Sorry to set off a firestorm.
You’re quite confused. NP is (at least) a superset of P, and not all problems in P can be solved in linear time (for example, sorting an arbitrarily long list of random numbers). I think you meant something like O(n^(1000^1000))?
My point is simply to show that even linear-time problems may be computationally intractable.
The definition of O(n) is: f is in O(n) so long as |f(n)| <= M * |n| for some constant M.
Likewise, the definition of O(n * c) would be: f is in O(n * c) so long as |f(n)| <= M' * |n * c| for some constant M'.
As you can see, any function f which is in O(n * c) is also in O(n), and vice versa.
The entire point of complexity classes is to describe asymptotic behavior. If you want to describe something other than asymptotic behavior, find a different tool.
I do not disagree with the definition. But you shouldn't rigidly focus on the definition without considering the utility of the notation, and the purpose of the discussion.
Big O notation describes the asymptotic behavior of a function when the argument N being passed to it approaches infinity. This is why it is also known as asymptotic notation.
Now, since this thread is about practical consequence, there is a severe problem with glibly saying that n * 999^999^999^999^999 will ever remotely resemble n from a practical standpoint. You'll never be able to compute f(1), much less a value of n large enough to be limiting.
At any rate, it looks like we both agree that O notation doesn't help you here. My fault for bringing it up.
it sounds like you are irritated that you are being contradicted. i think the solution in this case is that you stop saying things that are flagrantly wrong. i am interested in "this particular semantic diversion". you have been taking a rather confident, definite tone in your various assertions and someone could easily get confused into believing there is legitimate content in your mathematical errors
by the "core of [your] argument" i assume you mean the idea that problems may be solvable in polynomial time but not necessarily quickly solvable in practice, therefore it is a simplification to call the elements of P "easy." that is of course indisputable, but i think the heuristic argument that P problems are easy is more forgivable than the mathematical error of saying O(cn) != O(n) because, like, y'know, asymptotics and stuff
"what if some NP-hard problems could be solved in O(n^(1000^1000))?"
That is polynomial time so those problems would be in P, but in practice they would be intractable.
It would be a major breakthrough (comparable to P=NP) if anyone could show that the intersection of NP and co-NP is equal to NP.
Some people tried to make an encryption system out of the knapsack problem (http://en.wikipedia.org/wiki/Merkle%E2%80%93Hellman_knapsack...). It makes a good read about how a promising cryptosystem was broken.
Some interesting tid-bit: Even if P != NP, it could still be that most instances of NP-hard problems are easy to solve. (I.e. it's possible that even for NP-hard problems the expected running time is polynomial for all realistic probability distribution of instances. For certain definitions of `realistic'.)
Edit: so with this in mind, is it safe to say that the NSA's mathematicians are probably the few individuals in the world most interested in this recent development ? Or, are there other types of problems out there that this proof attempts to address? (Commercial etc)
If we had some easy way to solve problems in NP though, I bet there would be tons of productive applications. I'll quote a friend of mine:
"That would transform life on earth, and multiply our technological development rate by a factor unimaginable.
There's no way of even estimating what could happen if that problem were solved, unless the polynomial conversion made the problem impossible.
....It would also solve the protein-folding problem and all of the quantum state problems. Money is nifty; immortality and a possible stardrive don't suck. The NP problem is the current barrier to human science. 'There's no way to simulate that' is a constant refrain around here."
An interesting way of looking at it is that a valid proof that P != NP would be a kick in humanity's balls comparable to Gödel's incompleteness theorem.
But as you say, P = NP would really make things too easy.
Well, if the opposite had been proven, P = NP, there would be titanic commercial opportunities, but it seems to be the opposite (as most people suspected).