complexity-theory Definition Complexity Class A complexity class is a set of computational problems “of related resource-based complexity”