Difference between revisions of "Complexity Zoo:T"
(Added TI) 
(→TI: Tensor Isomorphism: Removed claim about Delta_2 P since it was superfluous) 

Line 50:  Line 50:  
The class of problems that are polynomialtime Turing reducible to Tensor Isomorphism. Defined in [[zooref#gq19[GQ19]]]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).  The class of problems that are polynomialtime Turing reducible to Tensor Isomorphism. Defined in [[zooref#gq19[GQ19]]]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).  
−  Over any field F, contains [[Complexity Zoo:G#giGI]]  +  Over any field F, contains [[Complexity Zoo:G#giGI]]. As with Graph Isomorphism, the Tensor Isomorphism problem itself (say, over finite fields) is contained in [[Complexity Zoo:N#npNP]] as well as [[Complexity Zoo:C#coamcoAM]] (and indeed [[Complexity Zoo:S#szkSZK]]; the same results hold over arbitrary fields in the BSS model). So in particular, if Tensor Isomorphism is [[Complexity Zoo:N#npNP]]complete, then [[Complexity Zoo:P#phPH]] collapses. 
Many natural problems are TIcomplete, such as isomorphism of dtensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo)isometry of alternating matrix spaces, isomorphism of matrix pgroups of class 2 and exponent p, and equivalence of cubic forms [[zooref#gq19[GQ19]]].  Many natural problems are TIcomplete, such as isomorphism of dtensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo)isometry of alternating matrix spaces, isomorphism of matrix pgroups of class 2 and exponent p, and equivalence of cubic forms [[zooref#gq19[GQ19]]].  
    
+  
===== <span id="treebqp" style="color:red">TreeBQP</span>: [[Complexity Zoo:B#bqpBQP]] Restricted To Tree States =====  ===== <span id="treebqp" style="color:red">TreeBQP</span>: [[Complexity Zoo:B#bqpBQP]] Restricted To Tree States =====  
The class of languages accepted by a [[Complexity Zoo:B#bqpBQP]] machine subject to the constraint that at every time step t, the machine's state is exponentially close to a <i>tree state</i>  that is, a state expressible by a polynomialsize tree of additions and tensor products (together with complex constants and 0> and 1> leaf nodes).  The class of languages accepted by a [[Complexity Zoo:B#bqpBQP]] machine subject to the constraint that at every time step t, the machine's state is exponentially close to a <i>tree state</i>  that is, a state expressible by a polynomialsize tree of additions and tensor products (together with complex constants and 0> and 1> leaf nodes). 
Revision as of 19:41, 15 August 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
TALLY  TC^{0}  TFNP  Θ_{2}P  TI  Tower  TreeBQP  TREEREGULAR
TALLY: Tally Languages
The class of decision problems for which every 'yes' instance has the form 0^{n} (i.e. inputs are encoded in unary). If TALLY intersects NPC then P = NP [Mah82].
Contained in SPARSE.
TC^{0}: ConstantDepth Threshold Circuits
The class of decision problems solvable by polynomialsize, constantdepth circuits with unbounded fanin, which can use AND, OR, and NOT gates (as in AC^{0}) as well as threshold gates. A threshold gate returns 1 if at least half of its inputs are 1, and 0 otherwise.
A uniformity requirement is sometimes also placed.
TC^{0} contains ACC^{0}, and is contained in NC^{1}.
TC^{0} circuits of depth 3 are strictly more powerful than TC^{0} circuits of depth 2 [HMP+93].
TC^{0} circuits of depth 3 and quasipolynomial size can simulate all of ACC^{0} [Yao90].
There is a function in AC^{0} (explicitly given in [She08]), whose computation with TC^{0} circuits of depth 2 requires an exponential number of gates.
[NR97] give a candidate pseudorandom function family computable in TC^{0}, that is secure assuming a subexponential lower bound on the hardness of factoring. (See also [NRR01] for an improvement of this construction, as well as [Kha93].)
One implication is that, assuming such a bound, there is no natural proof in the sense of [RR97] separating TC^{0} from P/poly. (It is important for this that a function family, and not just a candidate pseudorandom generator, is computable in TC^{0}.) Another implication is that functions in TC^{0} are likely to be difficult to learn.
The permanent of a 01 matrix cannot be computed in uniform TC^{0} [All99].
In a breakthrough result [Hes01] (building on [BCH86] and [CDL01]), integer division was shown to be in U_{D}uniform TC^{0}. Indeed division is complete for this class under AC^{0} reductions.
TFNP: Total Function NP
The class of function problems of the following form:

Given an input x and a polynomialtime predicate F(x,y), output any y satisfying F(x,y). (Such a y is promised to exist.)
Can be considered as the functional analogue of NP ∩ coNP. Defined in [MP91].
Contained in FNP.
Subclasses include PPA, PPP, and PLS.
Θ_{2}P: Alternate name for P^{NP[log]}
TI: Tensor Isomorphism
The class of problems that are polynomialtime Turing reducible to Tensor Isomorphism. Defined in [GQ19]. Can depend on the field, and the relationship for TI over different fields is an open question, but many reductions hold for TI over any field (over finite fields or the rationals this can be done in the usual model of Turing machines; over arbitrary fields one can use the BSS model to formalize this).
Over any field F, contains GI. As with Graph Isomorphism, the Tensor Isomorphism problem itself (say, over finite fields) is contained in NP as well as coAM (and indeed SZK; the same results hold over arbitrary fields in the BSS model). So in particular, if Tensor Isomorphism is NPcomplete, then PH collapses.
Many natural problems are TIcomplete, such as isomorphism of dtensors for any fixed d ≥ 3, isomorphism of algebras, conjugacy of spaces of matrices, (pseudo)isometry of alternating matrix spaces, isomorphism of matrix pgroups of class 2 and exponent p, and equivalence of cubic forms [GQ19].
TreeBQP: BQP Restricted To Tree States
The class of languages accepted by a BQP machine subject to the constraint that at every time step t, the machine's state is exponentially close to a tree state  that is, a state expressible by a polynomialsize tree of additions and tensor products (together with complex constants and 0> and 1> leaf nodes).
More formally, a uniform classical polynomialtime algorithm generates a sequence of gates g^{(1)}, ... ,g^{(p(n))}. Each g^{(t)} can be either be selected from some finite universal basis of unitary gates (the choice turns out not to matter), or can be a 1qubit measurement. When we perform a measurement, the state evolves to one of two possible pure states, with the usual probabilities, rather than to a mixed state. We require that the final gate g^{(p(n))} is a measurement of the first qubit. If at least one intermediate state was more than distance 2^{Ω(n)} away from the nearest state of tree size at most p(n), then the outcome of the final measurement is chosen adversarially; otherwise it is given by the usual Born probabilities. The measurement must return 1 with probability at least 2/3 if the input is in the language, and with probability at most 1/3 otherwise.
Contains BPP, and is contained in BQP.
Defined in [Aar03b], where it was also shown that TreeBQP is contained in the third level of PH, which might provide weak evidence that TreeBQP does not equal BQP.
TREEREGULAR: Regular TreeValued Languages
Same as REG, except that now the inputs are trees (say, binary trees) instead of strings. Each vertex is labeled with a symbol from a fixed alphabet. Evaluation begins at the leaves and proceeds to the root. The state of the finite automaton at each vertex v is a function of (1) the states at v's children (if any), and (2) the symbol at v. The tree is in the language if and only if the automaton is in an 'accept' state at the root.
See [Koz92] for example.