# Difference between revisions of "Complexity Zoo:G"

m (1 revision: Complexity zoo import.) |
(→GI: Graph Isomorphism: Added some interesting GI-complete problems, as well as refs to ZKT85, Gri83, Gro12) |
||

Line 66: | Line 66: | ||

The [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] <i>problem</i> itself (as opposed to the set of problems Turing reducible to [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]]) is contained in [[Complexity Zoo:N#np|NP]] as well as [[Complexity Zoo:C#coam|coAM]] (and indeed [[Complexity Zoo:S#szk|SZK]]). So in particular, if [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] is [[Complexity Zoo:N#np|NP]]-complete, then [[Complexity Zoo:P#ph|PH]] collapses. | The [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] <i>problem</i> itself (as opposed to the set of problems Turing reducible to [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]]) is contained in [[Complexity Zoo:N#np|NP]] as well as [[Complexity Zoo:C#coam|coAM]] (and indeed [[Complexity Zoo:S#szk|SZK]]). So in particular, if [[Complexity_Garden#graph_isomorphism|Graph Isomorphism]] is [[Complexity Zoo:N#np|NP]]-complete, then [[Complexity Zoo:P#ph|PH]] collapses. | ||

+ | |||

+ | Many natural problems are GI-complete (polynomial-time Turing equivalent to GI); for a partial list see the [https://en.wikipedia.org/wiki/Graph_isomorphism_problem#GI-complete_and_GI-hard_problems 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 [[zooref#gri83|[Gri83]]], and isomorphism of context-free grammars (for all of these and further references see [[zooref#zkt85|[ZKT85]]]). Conjugacy of semisimple Lie algebras given by matrices is also GI-hard, and is even GI-complete assuming one can compute relevant eigenvalues [[zooref#gro12|[Gro12]]]. | ||

See [[zooref#kst93|[KST93]]] for much more information about GI. | See [[zooref#kst93|[KST93]]] for much more information about GI. |

## Latest revision as of 16:55, 9 July 2019

*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^{0} -
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^{0}: Gap #AC^{0}

The class of functions from {0,1}^{n} 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^{0} is the ability to subtract, using the constant -1.)

Equals DiffAC^{0} under logspace uniformity [ABL98].

##### GapL: Gap Logarithmic-Space

Has the same relation to L as GapP does to P.

##### 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

- guessing s(n) bits, then
- 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^{2}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 Δ_{2}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.