P-complete
Sign in to saveIn computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.
~10 min read
Article
6 sectionsContents
- Motivation
- Reductions
- P-complete
- '''P'''-complete problems
- Notes
- References
In computational complexity theory, a decision problem is P-complete (complete for the complexity class P) if it is in P and every problem in P can be reduced to it by an appropriate reduction.
The notion of P-complete decision problems is useful in the analysis of which problems are difficult to parallelize effectively and which problems are difficult to solve in limited space, specifically when stronger notions of reducibility than polytime-reducibility are considered.
Connections
time complexity
Entity
NP-complete
Entity
EXPTIME
Entity
International Standard Book Number
Entity
digital object identifier
Entity
binary numeral system
Entity
International Standard Serial Number
Entity
graph theory
Entity
Turing machine
Entity
linear programming
Entity
lambda calculus
Entity
Conway's Game of Life
Entity
computational complexity theory
Entity
Stephen Cook
Entity
unary numeral system
Entity
NP
Entity
context-free grammar
Entity
GNU gzip
Entity
decision problem
Entity
P
Entity