complexity-theory Definition Complexity Class A complexity class is a set of computational problems of related resource-based complexity. Order LSPACE NL P PSPACE EXPTIME NEXPTIME