Complete problems for deterministic polynomial time

Log space reducibility allows a meaningful study of complexity and completeness for the class P of problems solvable in polynomial time (as a function of problem size). If any one complete problem for P is recognizable in log k (n) space (for a fixed k), or requires at least n c space (where c depends upon the program), then all complete problems in P have the same property. A variety of familiar problems are shown complete for P, 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.

Authors

• Neil D. Jones
• William T. Laaser

Keywords

No keywords are indexed for this paper.