1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

P Versus NP Problem

  1. Nov 29, 2013 #1
    Hey All,

    I was wondering if anyone had ever done any work on the P v NP problem that involved expressing P = NP as a limit

    I am sure there are 1001 "proofs" submitted every day to official boards at math institutes so I thought I would come here to get a handle on the state of the problem of P and NP.

    My reasoning tells me that at some point in time P will equal NP because our ability to solve problems right now is limited. If you imagine in thousands or millions of years, if we are still around surely given the rate at which we solve problems and invent technology we would be able to solve anything as quickly as we can verify it now. Bare with me I know this sounds like hocus pocus.

    The RSA used to pay money if members of the public could factorize huge numbers. http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

    They actually had to make a few payouts because by harnessing the CPUs of thousands of machines they could compute the factors in about 6 months, despite it being computationally infeasible.

    Given the rate at which CPUs get more powerful and given that they haven't been around very long is it feasible to say that at some point in time we will be able to factorize huge numbers as quickly as we can verify them?

    Is it fair to say that at some point in time P = NP - is there any school of thought regarding this?
  2. jcsd
  3. Nov 29, 2013 #2


    User Avatar
    Science Advisor

    P v NP refers to whether there exists an algorithm which grows at polynomial rate. It has nothing to do with CPU power. If P = NP in a million years time in the future, that means that P = NP today.
  4. Nov 29, 2013 #3
    How can an algorithm grow?
  5. Nov 29, 2013 #4


    User Avatar
    Science Advisor

    Wikipedia Analysis of Algorithms. Specifically Order of growth.

    Another thing to point out. We use the concept of time complexity. How much "time" an algorithm uses is determined by the number of steps, not the number of seconds it takes. So even if CPUs get faster, it has no bearing on the order.
    Last edited: Nov 29, 2013
  6. Nov 29, 2013 #5
    Do you mean the time it takes an algorithm to compute something grows? or the algo itself?
  7. Nov 29, 2013 #6


    User Avatar
    Science Advisor

    If n is the length of the string used as input, we estimate the number of elementary operations need to solve the problem with the algorithm. Then we get a (asymptotical) function in n. It's how fast that function grow as n approaches infinity.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook