P, NP, NPC...


Problem that can be solved in polynomial time. Something like O(n^k). It could also be defines as the class of problems with "efficient solutions".


Problem that can be solved in non-deterministic polynomial time. Something like O(e^n). It could also be defined as the collection of problems that have "efficiently verifiable solutions".

NP Hard

If any algorithm for solving NP Hard problem can be translated to one for solving NP Problem. Or in otherwords "At least as hard as NP Problem".

NP Complete

NP + NP Hard. Or more easily some would say "a problem x that is in NP is also in NP-Complete if and only if every other problem in NP can be quickly (ie. in polynomial time) transformed into x." This means that solution to a NP Complete problem in polynomial time means solution to other NP problems.


The problem "P=NP?" is one of the most important Open Problem in Computer Science.

P = NP means that for every problem that has an "efficiently verifiable solution", we can "find that solution efficiently" as well. But it hasnt proved yet.


One-way functions are easy to compute but hard to invert. Although there are several candidates for which no good (i.e. quick) reverse algorithms are currently known, it has not yet been proven that any function exists for which no such reverse algorithms exist.If one-way functions do not exist then secure public key cryptography is impossible.