Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical.
I agree about the philosophical questions, but don't they also rely on the practical ramifications of the question?
"is judging creativity as easy as being creative"
What if P=NP, and for some problem there is a practical polynomial algorithm for checking a solution but only an impractical polynomial algorithm for finding a solution? What I mean is that the philosophical ramifications also depend on the assumption that polynomial~easy.
>n^3 or n^4 might already be considered impractical in many situation
You can always make these arguments for large enough N and short enough time constraints. It is an argument that as an engineer I sympathize with, but as a computer scientist I cannot endorse. The question of P=?NP is a mathematical and philosophical question. The problem of O(N) algorithms being too slow for situation X is an engineering question.
So while I recognize and even sympathize with you point, I do not think it detracts from the fundamental importance of the question at stake.
True, there is the engineering aspect, but I didn't mean that, I was talking about the same fundamental philosophical question you were.
That is, "are there problems for which we can easily verify a solution but not easily find one". P=?NP is only relevant to this philosophical question, if we accept that "polynomial" is synonymous with "easy". That is a widely accepted statement, but not entirely obvious. As it was said in the linked poll, even a polynomial running time could hide contants so large, that it is prohibitively large not just today but anytime in the future until the universe collapses upon itself. On the other hand there can be NP-hard problems for which we can find arbitrarily close approximations in reasonable time. The question is how well are our theoretical efforts capturing this intuition.
> Well, n^3 or n^4 might already be considered impractical in many situation and even linear time algorithms might have huge constants that make them impractical.
Ah, so you now you can see how pathetic our understanding of computational complexity is when we consider algorithms that are linear sometimes impractical but we cannot show we can do better than an exponentially worse off bound for SAT instances (Today's best SAT algorithms run in time 2^O(n)).
I agree about the philosophical questions, but don't they also rely on the practical ramifications of the question?
"is judging creativity as easy as being creative" What if P=NP, and for some problem there is a practical polynomial algorithm for checking a solution but only an impractical polynomial algorithm for finding a solution? What I mean is that the philosophical ramifications also depend on the assumption that polynomial~easy.