The class of decision problems for which a "yes" answer can be verified by
For example, GC(p(n),P) = NP where p is a polynomial.
Defined in [CC93].
Umans [Uma98] has shown that given a DNF expression Φ, the Shortest Implicant problem is GC(log2n, coNP)-complete.
No class.