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.

7more comments