complexity theory
Noun
Meaning
complexity theory (uncountable)
(computer science) The study and classification of decision problems by the computational resources—such as time and space—needed by the programs that solve the problems.
The professor of complexity theory says that the problem can be solved in polynomial time.
Related terms
Examples
Computational complexity theory main A representation of the relation among complexity classes Complexity theory considers not only whether a problem can be solved at all on a computer, but also how efficiently the problem can be solved.
Complexity theory studies systems and properties of the latter type.