Class Description

GC(s(n),C): Guess and Check

The class of decision problems for which a "yes" answer can be verified by

1. guessing s(n) bits, then
2. verifying the answer in complexity class C.

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(log²n, coNP)-complete.

Linked From

No class.