Log space reducibility allows a meaningful study of complexity and completeness for the class of problems solvable in polynomial time (as a function of problem size). If any one complete problem for is recognizable in logk(n) space (for a fixed k), or requires at least nc space (where c depends upon the program), then all complete problems in have the same property. A variety of familiar problems are shown complete for , including context-free emptiness, infiniteness and membership, establishing inconsistency of propositional formulas by unit resolution, deciding whether a player in a two-person game has a winning strategy, and determining whether an element is generated from a set by a binary operation.
