I know that there are several problems for which a small change in the problem statement would result in a big change in its (time) complexity, or even in its computability.
An example: The Hamiltonian path problem defined as
Given a graph, determine whether a path that visits each vertex exactly once exists or not.
is NP-Complete while the Eulerian path problem defined as
Given a graph, determine whether a trail that visits every edge exactly once exists or not.
is solvable in linear time with respect to the number of edges and nodes of the graph.
Another example is 2-SAT (polynomial complexity) vs K-SAT (NP-complete) although someone could argue that 2-SAT is just a specific case of K-SAT.
What do you call this kind of problems –if they even have a name? Can someone provide a list of other examples or some references?