5
$\begingroup$

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.

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ 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. $\endgroup$
    – B. Bischof
    Commented Feb 26, 2012 at 5:49
  • 1
    $\begingroup$ 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. $\endgroup$
    – Yemon Choi
    Commented Feb 26, 2012 at 7:33
  • 7
    $\begingroup$ If the change from "wanting real solutions" to "wanting integer solutions" seems small, then one may need stronger lenses. $\endgroup$
    – Yemon Choi
    Commented Feb 26, 2012 at 10:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – Gerry Myerson
    Commented Feb 28, 2012 at 22:22
  • 1
    $\begingroup$ Meta discussion - tea.mathoverflow.net/discussion/1314/… $\endgroup$
    – François G. Dorais
    Commented Feb 29, 2012 at 2:53

5 Answers 5

Reset to default
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ This is very common, for example the mean ergodic theorem (Von-Neumann) vs. the pointwise ergodic theorem (Birkhoff). $\endgroup$
    – Asaf
    Commented Feb 26, 2012 at 7:22
  • 3
    $\begingroup$ Always good to see love for Carleson's theorem, but I would debate that this is a "small change" ... $\endgroup$
    – Yemon Choi
    Commented Feb 26, 2012 at 9:59
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Not a small change, in my opinion $\endgroup$
    – Yemon Choi
    Commented Feb 26, 2012 at 10:30
0
$\begingroup$

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

Improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged .