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