Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie
Hi there,
There is an issue with role permissions that is being worked on at the moment.
If you are having trouble with access or permissions on regional forums please post here to get access: https://www.boards.ie/discussion/2058365403/you-do-not-have-permission-for-that#latest

Millennium Prize Problems, I'm a winner!

  • 19-08-2006 5:17pm
    #1
    JoeB-
    Registered Users, Registered Users 2 Posts: 689 ✭✭✭


    Hi

    I saw the thread on the Millennium Prize Problems from the Clay Mathematics Institute... I was interested and looked it up in Wiki...

    The first problem is...
    P versus NP
    Main article: Complexity classes P and NP
    The question is whether there are any problems for which a computer can verify a given solution quickly, but cannot find the solution quickly. This is generally considered the most important open question in theoretical computer science.


    I would have thought that the public and private key cryptography system represents such a problem. i.e a computer cannot factor a large number into its constituent primes quickly but it can multiply the two primes given to verify the solution in a flash! :) That's what the public and private key cryptography system is based on....

    Do I win a million? or did Wiki give me the wrong text for the first problem? or am I somehow a muppet? :o

    Cheers
    Joe

    (moderators please don't delete this as I need it to verify my millionaire status!)


Comments

  • #2
    Son Goku
    Closed Accounts Posts: 1,475 ✭✭✭Son Goku


    An NP problem is one which involves an easy computation, which has to performed a million times.
    An example would be public key cryptography.

    A P problem is one which is done in one step relatively quickly. An example would be image generation or adding/multiplying two numbers.

    If P=NP is true, it means there is an algorithm out there which can get a number's factors as easily as it could check if two factors were a solution.

    It would mean all repetitive algorithms are really just a bad way of doing a non-repetitive one.

    Like all the Millennium problems, it is rock hard in terms of difficulty.
    (They are the seven hardest mathematical problems to this day)
    Solving any of them would require a very deep knowledge of the respective field of maths.


  • #3
    ecksor
    Moderators, Social & Fun Moderators Posts: 10,501 Mod ✭✭✭✭ecksor


    I seem to recall some famous mathematician commenting that if an amateur was to solve a millennium prize problem then the P=NP question would be the most likely.


  • #4
    Gone West
    Registered Users, Registered Users 2 Posts: 6,374 ✭✭✭Gone West


    ecksor wrote:
    I seem to recall some famous mathematician commenting that if an amateur was to solve a millennium prize problem then the P=NP question would be the most likely.
    Keith Devlin?
    I'd be inclined to agree somewhat, however what the OP has recognised is not the P=NP solution, as Son Goku has explained.
    Hard luck :)

    It is still extremely unlikely that an amateur or even a non expert on the top of their game in these exact sub-fields will ever solve a millunnium problem.


Advertisement