While is a theoretical programing language defined in [jon98], it is a way to define P syntactically and a syntactic restriction of WHILE is exactly L. The important point is that those two languages are powerful enough to simulate all of P (and L) and when we write a program in this language we never need to prove its time (space) complexity, since the language guarantees it!
In While, inputs are composed only of lists (in a lisp-way where a list is either an empty list or a pair of its first element and its tail) and the elements of the list and variables are only pointers to lists.
A program contains global variables and procedures.
There are three function primitives: tail, head, and cons(h,t), which respectively give the first value of a list, the tail of the list and a list the first element of which is h and the rest of the list is t. We can also call defined procedures.
We can then define WHILE/cons-rec which is WHILE without the "cons" primitive and procedure call[#]. It is equivalent to L. The trick to do the computation in logspace is that without recursion we only need to save a fixed number of variables which are only pointers to part of the input, so they only take logspace. Since any logspace TM can avoid having a work tape by having a fixed number of reading head on his input, we can simulate logspace TM by using a variable for every reading head. (The binary string is coded as a list of () for 0 and (()) for 1, so equality can be checked trivially)
[#] in fact we only need to forbid recursive call, hence the name, but when we lose recursion we can assume there is no procedure call w.l.o.g, in fact in [jon98] WHILE is first defined without procedure call and procedure are defined later, but this presentation may be more easy to understand and at least more general.
We can then also define WHILErec/cons which is WHILE without "cons" primitive but with procedure calls, and hence recursion. It is equivalent to P. The trick to do a computation of a WHILErec/cons in P is to memoize the couple (global variables, input) when a procedure is called and the value of the globals variable when the procedure end, since we don't have cons, only a polynomial number of call will really be executed and we can detect loop.Simulating P in WHILErec/cons is quite more subtle, P TM are equivalent to some counter machine wich can easily be simulated by WHILE programs with cons, and then we can simulate the cons thanks to the call stack.
The class that started it all.
The class of decision problems solvable in polynomial time by a Turing machine. (See also FP, for function problems.)
Defined in [Edm65], [Cob64], [Rab60], and other seminal early papers.
Contains some highly nontrivial problems, including linear programming [Kha79] and finding a maximum matching in a general graph [Edm65].
Contains the problem of testing whether an integer is prime [AKS02], an important result that improved on a proof requiring an assumption of the generalized Riemann hypothesis [Mil76].
A decision problem is P-complete if it is in P, and if every problem in P can be reduced to it in L (logarithmic space). The canonical P-complete problem is circuit evaluation: given a Boolean circuit and an input, decide what the circuit outputs when given the input.
Important subclasses of P include L, NL, NC, and SC.
P is contained in NP, but whether they're equal seemed to be an open problem when I last checked.
Efforts to generalize P resulted in BPP and BQP.
The nonuniform version is P/poly, the monotone version is mP, and versions over the real and complex number fields are PR and PC respectively.
In descriptive complexity, P can be defined by three different kind of formulae, FO(lfp) which is also FO()], and also as SO(Horn)
P queries are exactly the one that can be written in the While/cons languages.
P is the class of decision problems solvable by a (logspace) uniform family of polynomial-size Boolean circuits.
P can be computed by interactive protocols (see IP) where the verifier runs in log space (see L and BPL) [GKR15].
