Easy and Hard problems in Mathematics Modified question:
I would like to know some examples of problems in Mathematics, for pedagogical purposes, which do not involve difficult techiques to solve the problem but with a change of context turns them into monstrous-unimaginably difficult to solve problems. 
By changing the context I mean, by changing one class of objects in the problem to a related 
class of objects. For example, from directed graph to undirected graph or Zygmund class to 
Log-lipshitz class. By changing a 'less-than problem' to 'greater-than problem'. From 2-case 
problem to 3-case problem. There are plenty of such examples in Theoretical Computer Science or Computational Complexity theory. I need some examples in Mathematics. Lot of examples fall in this category but I am looking for only extreme examples like the ones I stated below. Since, this question is asked for pedagogical purpose it would be interesting if there is a story behind the problem.
Examples of problems: 


*

*Linear Programming to integer linear programming

*2-coloring to 3-coloring

*Eulerian graph to Hamiltonian graph

*Undirected graph case to directed graph case in Shannon's switching game

*2-SAT to 3-SAT


One thought which motivated me to pose this question is: what if Konigsberg problem has been
formulated as a vertex problem. Would Leonard Euler get inspried to create graph theory? No 
doubt, history speaks differently as Konigsberg problem is stated in terms of edges. Not only
Euler solved this problem but created a branch of mathematics out of it! And I am not sure what turn of events would have taken place had the problem been posed in terms of vertices. 
IMHO, there are look-alike easy problems and hard problems coexisting but it is the easy problems which saved mathematicians day and hard ones which gave them incentive to work harder.
Some pointers for hardness of problem: problems which need sophisticated tools, techniques which diverge from the routine ones, radical thinking or bold ideas to solve the them, like Poincare conjecture. Or, those problems which do not have adequate tools yet to attempt them, like (NP=P?).  
I would appreciate any answers in this direction. Thank you in advance. 
 A: Finding the $\ell_p$ operator norm of a matrix is easy for $p=1,2,\infty$, but it is NP-hard for any other $p$ (see this discussion, for example).
A: Changing $L^2$ convergence to almost everywhere convergence (of the Fourier series of an $L^2$ function) takes (essentially) the rather easy Riesz-Fischer theorem into the very hard Carleson's theorem. 
A: Changing the question from "integral quadratic form represents zero" to "real quadratic form almost represents zero", changes the classical theorems (which eventually sum up to the Hasse-Minkowski theorem) to the Oppenheim conjecture, proved by Margulis in the late 80s, by completely different methods (instead of algebraic number theory, one uses Homogeneous Flows).
A: Finding real solutions to an elliptic curve compared to finding integer solutions.
A: Let C be a finite collection of finite sets.  Further let C be closed under union.  Is it always the case that there is an element x which is in at least half the members of C?
The answer to this question is no.  If, however, the union of C is required to be nonempty, then the answer is unknown to me, and I suspect to many others.  (Look up union closed sets conjecture.)
Gerhard "Ask Me About System Design" Paseman, 2012.02.26
