A hypothesis in theoretical
computing science regarding the running time of
algorithms.
P refers to PTIME, the class of algorithms that have running time proportional to a polynomial in terms of the input size.
NP refers to NPTIME, the class of nondeterministic algorithms with polynomial running time in terms of the input size.
Stephen A. Cook and others obtained some interesting results in NP problems; in particular, in 1971 he showed that satisfiability is NP-complete. NP-complete problems are the 'hardest' in NP: if a polynomial time deterministic algorithm is found for one of them, it can be adapted to work for any problem in NPTIME. In short, it would prove that P = NP.
30 years on, this is considered immensely unlikely, but no formal refutation of the possibility has yet been found.