MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

closed as not a real question by Ryan Budney, Robert Israel, Andreas Thom, Yemon Choi, Oscar Randal-Williams Feb 26 '12 at 11:21

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

I'm guessing the words "small change" are I'll defined enough to get this question closed. That being said, when you prove theorems, you have some assumptions on the objects of study, in a huge number of cases removing an assumption makes the theorem not just more difficult, but plain wrong. But it's at a fundamental level. An example of this is Fermat's Last theorem(I went with the most obvious example possible), if you take R or C rather than Z, solutions exist and the proof is fairly straightforward. – B. Bischof Feb 26 '12 at 5:49
I just voted to close as "not a real question" but in hindsight I think "subjective and argumentative" is nearer the mark. A lot of these so-called small changes are in fact BIG changes, in my opinion. – Yemon Choi Feb 26 '12 at 7:33
If the change from "wanting real solutions" to "wanting integer solutions" seems small, then one may need stronger lenses. – Yemon Choi Feb 26 '12 at 10:27
I take it you are hoping to get the question reopened. Perhaps you should start a thread on the meta site where there could be a discussion of how the question might be made more acceptable on MO. I'm not sure that a change in the title suffices. – Gerry Myerson Feb 28 '12 at 22:22
Meta discussion -… – François G. Dorais Feb 29 '12 at 2:53

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).

share|cite|improve this answer

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.

share|cite|improve this answer
This is very common, for example the mean ergodic theorem (Von-Neumann) vs. the pointwise ergodic theorem (Birkhoff). – Asaf Feb 26 '12 at 7:22
Always good to see love for Carleson's theorem, but I would debate that this is a "small change" ... – Yemon Choi Feb 26 '12 at 9:59

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).

share|cite|improve this answer

Finding real solutions to an elliptic curve compared to finding integer solutions.

share|cite|improve this answer
Not a small change, in my opinion – Yemon Choi Feb 26 '12 at 10:30

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.