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

What's P and NP?

  1. Feb 15, 2005 #1

    VietDao29

    User Avatar
    Homework Helper

    Hi,
    I saw this in one of the thread here and I haven't seen this before.
    Can any of you guys help me understand what it is? Or just show me a web-page that detailedly explain it? I surfed some and they somewhat confused me... :confused:
    Thanks very much, :smile:
    Viet Dao,
     
  2. jcsd
  3. Feb 15, 2005 #2

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

  4. Feb 15, 2005 #3

    Alkatran

    User Avatar
    Science Advisor
    Homework Helper

    an NP problem is one that takes a LOT of time to solve.

    Ie, if you have a list with 4 items, an NP problem would take c^4 iterations to solve it. With 8 items it would be c^8 (grows exponentially)

    A P problem isone that has a time 4^c, 8^c, depending on the list. (c is some constant)
     
  5. Feb 16, 2005 #4

    VietDao29

    User Avatar
    Homework Helper

    Hi,
    Thanks both of you. It's clearer now.
    Thanks,
    Viet Dao,
     
  6. Feb 16, 2005 #5
    This is actually a really bad way to describe NP. For one thing, just because a problem requires exponential time to solve, it doesn't mean the problem is in NP; it may be a more difficult problem than any problem in NP. And just because a problem is in NP, it doesn't mean it takes a long time to solve; all of the problems in P are also in NP.


    Basically, P and NP are concerned with what algorithms run in polynomial time. An algorithm runs in polynomial time if, given some function that describes how long the algorithm takes, you can find a polynomial larger than that function. A more intuitive explanation is that doubling the size of the problem always increases the amount of time it takes to solve it by a constant factor; for example, doubling the size of the problem means it takes four times as long to solve.

    Then we consider P to be the class of all problems that can be solved in polynomial time. And we consider NP to be the class of problems where, if you're given a possible solution to the problem, you can verify if that solution is correct or not in polynomial time.

    Now clearly if a problem is in P then the problem is in NP; if we know how to solve the problem in polynomial time, then we certainly know how to verify if a solution is correct in polynomial time. The more interesting question is, if a problem is in NP, is it in P? We don't know. That's what the whole P=NP business is about.
     
  7. Feb 17, 2005 #6

    VietDao29

    User Avatar
    Homework Helper

    Hi,
    So as I understand, any question which provides you a list of items. And ask you to pick up some of them, and all the picked items must be compatible. And a commondation for 100 students, who are picked from a lists of 400 is an example. Am I correct?
    Viet Dao,
     
  8. Feb 17, 2005 #7

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    An example of what?
     
  9. Feb 17, 2005 #8
    No, its not just about picking items from a list. It's about any problem where you're given some type of input and asked to produce some type of output. For example, you're given a list and asked to produce a sorted version of the list. Or you're given a graph and asked to find a Hamiltonian cycle in it.

    The problem of picking compatible students from a list is just a single example. It's clearly in NP, because if I give you a potential solution, there's a fast way to test if the solution is in fact correct. But it might not be in P; we don't know if there's a fast way to produce a correct list.
     
  10. Feb 18, 2005 #9

    VietDao29

    User Avatar
    Homework Helper

    Hi,
    Thanks Master Coda. I understand it now.
    Thanks very much, :smile:
    Viet Dao,
     
  11. Feb 18, 2005 #10

    honestrosewater

    User Avatar
    Gold Member

    Can you not incorporate the solution (ex. the Dean's list) into the decision-making process?
     
  12. Feb 18, 2005 #11
    You can. But won't really help you solve the problem given a different list of students. You can't incorporate a solution for every possible list, since there are an infinite number of possible lists.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: What's P and NP?
  1. P vs NP (Replies: 15)

  2. P=np refuted (Replies: 3)

  3. P = np formula (Replies: 7)

  4. A proof for P vs NP (Replies: 8)

  5. P Versus NP Problem (Replies: 5)

Loading...