What Is P and NP? - Explained by Viet Dao

[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,

 

[matt grime]

http://www.claymath.org/millennium/P_vs_NP/

 

[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)

 

[VietDao29]

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

 

[master_coda]

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)

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.

 

[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,

 

[matt grime]

An example of what?

 

[master_coda]

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,

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.

 

[VietDao29]

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

 

[honestrosewater]

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.

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

 

[master_coda]

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

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.