If I have a algorithm A that i have proven belongs to P can this algorithm also belong to the NPC class or is it strictly P? What about NP? P Belongs to NP right?
Thx for any help!
/Marthin
+5
A:
If P!= NP then P is not a subset of NPC, in fact they don't intersect. If P=NP, then P and NPC are the same. All P algorithms are part of NP though. Check the Wikipedia page for more information, and a diagram that explains exactly what you're asking.
If you can prove that P=NP, you will be very famous.
Carl Norum
2010-05-22 16:09:38
Thanks for clarifying!
Marthin
2010-05-22 16:12:27
@Carl: P is not a subset of NPC(I presume that means NP-Complete) depends on whether P = NP or not. If P != NP, then P and NPC do not intersect, otherwise they are the same! Please clarify that.
Moron
2010-05-22 18:53:28
@Moron, that's correct.
Carl Norum
2010-05-22 23:30:53
@Carl: I meant please edit your answer to clarify that.
Moron
2010-05-23 00:59:46
Never mind. I took the liberty to make that edit myself.
Moron
2010-05-23 20:49:49