Natural notion for computational hardness When I teach students concepts like intractable problems and efficient algorithms in discrete structures or data structures and algorithms, it is difficult for students to intuitively grasp somewhat artificial concepts of asymptotic time complexity and polynomial growth rates. Artificial $NP$-complete problems were known before the discovery of Cook's first natural $NP$-complete problem, which sparked huge interest in the field. Under some acceptable definition of natural:  


  What is the most natural way to express the computational hardness of natural problems to students who encounter the subject for the first time?


EDIT: Motivated by Marc's answer, it would be more natural to find how hard is the self reducibility of clique problem. For instance, How hard is it to reduce an instance of clique of input size $(1+ \epsilon)n$ to an instance of size $n$ using Turing reduction?.
Just what makes growth rates such as O(n&sup2;) artificial — just the fact that it isn't one specific monotonic function? Or is it the fact that it's a family of functions in itself, and not just some simple number which comes from something obvious about the problem?

At the very least, your students should be able to grasp the purpose, and in a sense the meaning, of asymptotic notation by observing how the tediousness of performing arithmetic scales with the size of the numbers &mdash; that it gets more tedious for larger numbers, and that adding two n-bit numbers is less tediuous than multiplying them. Hopefully they should percieve a difference! If they can, then you have got them where you want them. Point out that the difference is smaller when you have smaller numbers: obviously the difference is one which grows with instance size. Point out to them the nested iterations in the multiplication algorithm. And now you have motivated caring about the difference between O(n&sup2;) time and O(n) time. Get them to do matrix computations next to give them a taste of O(n&sup3;), and point out the nested iterations there. They should get the idea after that.

I would say that exponential-time versus poly-time often amounts to "searching through a combinatorial explosion versus performing a bounded number of nested iterations", which is about as natural a distinction as possible between approaches to solving problems (e.g. in computer programming). But you cannot motivate complexity of problems of any sort, to people who do not themselves spend time solving problems and so who have no taste for the idea that certain ways of solving things (or solving different kinds of problems) take different amounts of work, and that differences between algorithms come from some place. You can't convince someone of these things unless they can have enough "empathy" for the computer to viscerally feel the extra work that is being done in one algorithm, versus another; to be aware of the layers of computing or of searching which it is doing, to actually hope that the problem has enough structure to narrow the solution space beyond just nested loops. They must be able to appreciate the existentially Sisyphian futility of trying to solve instances of SAT just by looking forlornly for a solution brute-force. This sort of perspective comes from solving problems oneself, and being self-aware of what one is doing; and I think it is perfectly natural to ask how much the tediousness of the task (i.e. how many computations you are doing) scales with the size of the problem.

If your students can't grasp this, tell them that the "difficulty" of adding numbers by high-school techniques is rated as 1; that of multiplying numbers is rated as 2; that sorting an unordered list has a rating between 1 and 1.000001 if you do it in the right way; and that there are no techniques for solving SAT whose rating is less than infinity; and move on from there &mdash; because you're not likely to do much better than this pedagogically without inventing a novel complexity measure, or obtaining more engaged students.