Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Unsolved math problems?

  1. Feb 14, 2005 #1
    Does anyone have a list of decent sites which include a range of either unsolved mathematical problems, or unproven formulae? There used to be on liked from my employer's mathematical index, but it is no longer there. I understand that the possibility of doing something like finding all the zeros of the riemann zeta function is impossible for most of the world's population(including me), but regardless, I am curious as to where the mathematics train consistently runs into the wall. I'm mostly interested in the history of theory that went unproven for a long time and what it took (both time and ingenius mathematical concepts) to solve or prove these theories.

    Thanks.
     
  2. jcsd
  3. Feb 14, 2005 #2

    mathwonk

    User Avatar
    Science Advisor
    Homework Helper
    2015 Award

    here is some history on the famous and recently solved after 100 years, poincare conjecture.

    Background on the problem, by John Milnor:

    http://www.math.sunysb.edu/~jack/PREPRINTS/poi-04a.pdf

    As a second step, see Milnor's next article on the progress towards
    the conjecture & classifying three-manifolds:

    http://www.math.sunysb.edu/~jack/PREPRINTS/tpc.pdf )

    On the recent solution:

    Speaker: Jason Parsley, University of Georgia
    Title of talk: Introduction to the Poincare Conjecture

    Abstract: In 1904, Poincare conjectured that every closed,
    simply-connected three-dimensional manifold is homeomorphic to the
    three-sphere. This problem remained unsolved for almost 100 years.
    Recently, Perelman posted a couple of papers on the Ricci flow, an
    equation of manifolds evolving based on their curvature, that implied
    Poincare's conjecture was true.

    In this talk, we will start by defining all relevant terms, then briefly
    describe the history of the Poincare conjecture and mention analogs in
    higher dimensions. We touch on Thurston's Geometrization Program, which
    roughly says that there are exactly eight different types of geometries
    that are possible for three-dimensional manifolds. If time allows, the
    last few minutes will be devoted to how Hamilton and Perelman used
    Riemannian Geometry to attack this problem.


    *************************
    R. Jason Parsley
    VIGRE Postdoc
    Department of Mathematics
    University of Georgia
    706.542.2562
    *************************
     
  4. Feb 14, 2005 #3
    i think you deify mathematicians/profs too much. but just as there are good & bad dishwashers/janitors/7-11 attendants, i guess there are good & bad mathematicians. they're like everyone else really, some just don't like to admit it.

    anyway, the rest of the clay math problems (besides the poincare conjecture) here:
    http://www.claymath.org/millennium/

    other unsolved problems include the following:
    a. the invariant-subspace problem (= whether there is a separable, infinite-dimensional banach space on which every linear operator has an invariant subspace. i think it's a natural generalization of a theorem that burnside proved but i can't remember what it was)
    b. whether every finite group H occurs as the Galois group of a finite Galois extension of the field of rational numbers. shafarevich proved this for solvable H & others (like hilbert) proved other special cases but the general problem is still unsolved.
     
  5. Feb 14, 2005 #4

    honestrosewater

    User Avatar
    Gold Member

    mathworld lists several problems and links.
     
    Last edited: Feb 14, 2005
  6. Feb 14, 2005 #5

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    They give a bad example for an NP = P problem. They give the example of picking 100 students from a list of 400, but that certain pairs of students can't both be picked. Here's a polynomial time for that one:

    1: Take input and create a list of the students alongside the students they are incompatible with.
    IE if roger can't go with tom, and the list is roger, tom, and becky, we get:
    Roger -> tom
    tom -> roger
    Becky

    2: Create a variable N and set it to 0. Then loop step 3 while remainingstudents > 0 and acceptedstudents < requirement

    3: Construct a loop which goes through the list of students adding them to the list

    3a: For(int m = 0, remainingstudents > m && acceptedstudents < requirement, m++)
    -For the non Java types, that means start m at 0, check if the conditions are met, and for every new iteration of the loop, increase m by 1.

    3b: Check if the number of students disallowed by the current student is equal to n.
    If it is then add the student to the accepted list and remove all the students disallowed by this student from the entrance list. (adjust m as necessary)

    3c: end of loop

    4: end of loop involving n

    5: Return wether or not the number of accepted students is at least the amount of needed students



    There. That will run in...

    n goes from 0 to a maximum of the number of students - 1
    m goes from 0 up to at most the number of students
    in the worst case scenario, where everyone is paired with everyone, removing students from the list will take the ~number of students squared operations. But n and m would not be looped at all, but I will just say that there can be a squared time inside that loop.

    Final time (overestimated) ~ O(x^4)
    (n from 0 to x, m from 0 to x, removing from list is (0 to ~x, 0 to x))

    The logic behind this is to add any student who is paired with very few students. By adding this student you are forcing the exit of another student who would force the exit of at least, if not more, students. This method should work for all inputs.
     
  7. Feb 14, 2005 #6
    I don't think your algorithm will actually work. It sounds like an algorithm that might find the correct solution, but might also fail when a solution exists.
     
  8. Feb 14, 2005 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Ah, but the greedy algorithm doesn't always work!

    Here's an example where we try to pick three students out of 7. Here's the list of unacceptable pairs:

    14 15 16 17 24 25 26 27 34 35 36 37 56 57 67

    So, for example, 14 means that 1 and 4 aren't compatable.

    Now, here's the counts of how many students are incompatable with a selected student:

    1 4
    2 4
    3 4
    4 3
    5 5
    6 5
    7 5

    Here, the greedy pick is to first accept student #4. This means we cannot pick students 1, 2, or 3. Therefore, we must also accept two of the students numbered 5, 6, and 7, but they are all incompatable with each other!

    The only solution here is to accept students 1, 2, and 3.
     
  9. Feb 15, 2005 #8
    Nice points, but I think it's a little worse than that.

    For simplicity let's call two students that can't be paired, enemies. If every student has at least 1 enemy this algorithm, as specified, fails to add any students to the accepted list.

    In this case N (or is it n?) never changes; it stays at 0. In fact it doesn't appear that n/N changes even if a student is removed from the candidate list and added to the accepted list. However, it does look like there is some kind of general plan to increment n/N; but when or why? That's an important detail.

    There's not much point to guessing what was intended since "obvious" choices of what was intended lead to incorrect algorithms as well.
     
  10. Feb 15, 2005 #9
    check these out:
    -- extend the mathematical model of general equilibrium theory to include price adjustments (introduce dymanics into economics)
    -- is there a polynomial-time algorithm over the real numbers which decides the feasibility of the linear system of inequalities Ax >= b?
    -- can a zero of n polynomial equations in n unknowns be found approximately, on the average, in polynomial time with a uniform algorithm?
    -- what are the limits of intelligence, both artificial and human?

    those are from smale's article referenced in that mathworld page. there were 18 problems in total; some are on the clay list (navier-stokes equations, riemann hypothesis, poincare conjecture) & i don't really get the other ones
     
  11. Feb 15, 2005 #10

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    14 15 16 17 24 25 26 27 34 35 36 37 56 57 67
    Create list
    1 - 4, 5, 6, 7
    2 - 4, 5, 6, 7
    3 - 4, 5, 6, 7
    4 - 1, 2, 3
    5 - 1, 2, 3, 6, 7
    6 - 1, 2, 3, 5, 7
    7 - 1, 2, 3, 5, 6

    I see the problem now. They're blocking the same people! Well, I guess I got snookered. Damn. Hmmmm problem is interesting now! :eek:

    I know the problem is apparently unsolveable, but there's nothing like an unsolveable problem to learn from. At least if I encounter this problem I have a "try it quick then try it hard" method

    I'm thinking of perhaps only counting equal sets once. But that can be beaten by adding 8 and 9 as enemies of eah other, 1 and 2... Perhaps grouping similar sets together... to get 3 * the set / 4... But then we need to sort since it's not integer...
     
  12. Feb 17, 2005 #11
  13. Feb 17, 2005 #12
    Check out your uni library. I saw a book yesterday on unsolved problems (twas yellow, by a Russian professor i think, or Italian), there are quite a few. Comes with commetary as well which is good! :D

    Take care.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Unsolved math problems?
  1. Unsolved Problem (Replies: 15)

Loading...