Complexity Zoo:G

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

---

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

---

GA - GAN-SPACE(f(n)) - GapAC⁰ - GapL - GapP - GC(s(n),C) - GCSL - GI - GLO - GPCD(r(n),q(n)) - G[t]

GA: Graph Automorphism

Can be defined as the class of problems polynomial-time Turing reducible to the Graph Automorphism problem.

Contains P and is contained in GI.

See [KST93] for much more information about GA.

---

GAN-SPACE(f(n)): Games Against Nature f(n)-Space

The class of problems decidable by an O(f(n))-space Turing machine with two kinds of quantifiers: existential and randomized.

Contains NSPACE(f(n)) and BPSPACE(f(n)), and is contained in AUC-SPACE(f(n)).

By linear programming, GAN-SPACE(log n) is contained in P.

---

GapAC⁰: Gap #AC⁰

The class of functions from {0,1}ⁿ to integers computable by constant-depth, polynomial-size arithmetic circuits with addition and multiplication gates and the constants 0, 1, and -1. (The only difference from #AC⁰ is the ability to subtract, using the constant -1.)

Equals DiffAC⁰ under logspace uniformity [ABL98].

---

GapL: Gap Logarithmic-Space

Has the same relation to L as GapP does to P. (And therefore, has the same relation to #L as GapP does to #P.)

The determinant is GapL-complete [Vin91] [Dam91] [Tod91] ([MV97] also gave a new, self-contained proof). See also the corresponding decision class DET

---

GapP: Gap Polynomial-Time

The class of functions f(x) such that for some NP machine, f(x) is the number of accepting paths minus the number of rejecting paths.

Equivalently, the closure of the #P functions under subtraction.

Defined in [FFK94] and independently [Gup95].

---

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.

---

GCSL: Growing CSL

The class of languages generated by context-sensitive grammars in which the right-hand side of each transformation is either strictly longer than the left-hand side or the left-hand side consists of the start symbol.

Defined in [DW86] and shown to be contained in LOGCFL (and therefore in P among others).

Shown to be equivalent to Acyclic CSL in [Nie02].

---

GI: Graph Isomorphism

Can be defined as the class of problems polynomial-time Turing reducible to the Graph Isomorphism problem.

Contains GA and is contained in Δ₂P.

The Graph Isomorphism problem itself (as opposed to the set of problems Turing reducible to Graph Isomorphism) is contained in NP as well as coAM (and indeed SZK). So in particular, if Graph Isomorphism is NP-complete, then PH collapses.

Many natural problems are GI-complete (polynomial-time Turing equivalent to GI); for a partial list see the Wikipedia page. While many of these are GI for a restricted class of graphs, some surprising GI-complete problems are: isomorphism of finite automata, isomorphism of commutative class 3 nilpotent semigroups, isomorphism of algebras over a field whose radical squares to zero and whose radical quotient is abelian [Gri83], and isomorphism of context-free grammars (for all of these and further references see [ZKT85]). Conjugacy of semisimple Lie algebras given by matrices is also GI-hard, and is even GI-complete assuming one can compute relevant eigenvalues [Gro12].

See [KST93] for much more information about GI.

---

GLO: Guaranteed Local Optima

The class of NPO problems which have the property that for all locally optimal solutions, the ratio between the values of the local and global optima is upper-bounded by a constant.

Defined in [AP95], where it was also shown that GLO is strictly contained in APX.

[KMS+99] showed that MaxSNP is not contained in GLO.

---

GPCD(r(n),q(n)): Generalized Probabilistically Checkable Debate

Same as PCD(r(n),q(n)), except that now the verifier is allowed nonadaptively to query O(q(n)) rounds of the debate, with no restriction on the number of bits it looks at within each round.

Defined in [CFL+93], who also showed that PCD(log n, q(n)) = GPCD(log n, q(n)) for every q(n).

---

G[t]: Stratification of Fixed-Parameter Tractable Problems

(Basically) the class of decision problems of the form (x,k) (k a parameter), that are solvable by a parameterized family of circuits with unbounded fanin and depth t. A uniformity condition may also be imposed.

Defined in [DF99], which should be consulted for the full definition.

Uniform G[P] (i.e. with no restriction on depth) is equal to FPT.