problems.

Defining complexity classes

The definitions of the complexity classes NP, PSPACE, and EXPTIME do not involve reductions: reductions come into their study only in the definition of complete languages for these classes. However, in some cases a complexity class may be defined by reductions. If C is any decision problem, then one can define a complexity class C consisting of the languages A for which . In this case, C will automatically be complete for

1.Previous
3.Next