>>10955604P stands for polynomial time, and in particular, deterministic polynomial time. It’s the class of functions/algorithms (represented as strings encodings of Turing machines) that take at most polynomially many deterministic steps to run. A step is defined as reading a symbol, changing state, writing a symbol, and moving the tape head. Deterministic here means that provided the same machine and input, the computation (the series of reads, state changes, and tape positions) of two distinct instances of running machine M on input x are guaranteed to be exact same.
NP stands for non-deterministic polynomial time. It has two equivalent characterizations: it is problems that can be solved in polynomial time provided there is non determinism, or it’s the problems that given a proposed solution to a problem, one can verify it solves the problem in P (that is, in deterministically polynomial steps). Non determinism here has many interpretations that end up being equivalent, but you can think of it as if the machine just made a series of succinct guesses at the beginning and ran a deterministic algorithm for the rest. Now, we know P NP, but there are a class of problems that lie in NP yet are conjectured to not lie in P, and those are NP-complete problems. There’s a fundamental puzzle-like difficulty that anyway you slice it, you have no better methods than to enumerate all possibilities and try them. There’s more to explain here, but these are the basic differences. These definitions inform some of the very basic proof techniques used in complexity, particular reductions.
