What's P and NP?

1. Feb 15, 2005

VietDao29

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...
Thanks very much,
Viet Dao,

2. Feb 15, 2005

matt grime

http://www.claymath.org/millennium/P_vs_NP/ [Broken]

Last edited by a moderator: May 1, 2017
3. Feb 15, 2005

Alkatran

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)

4. Feb 16, 2005

VietDao29

Hi,
Thanks both of you. It's clearer now.
Thanks,
Viet Dao,

5. Feb 16, 2005

master_coda

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.

6. Feb 17, 2005

VietDao29

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,

7. Feb 17, 2005

matt grime

An example of what?

8. Feb 17, 2005

master_coda

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.

9. Feb 18, 2005

VietDao29

Hi,
Thanks Master Coda. I understand it now.
Thanks very much,
Viet Dao,

10. Feb 18, 2005

honestrosewater

Can you not incorporate the solution (ex. the Dean's list) into the decision-making process?

11. Feb 18, 2005

master_coda

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.