TC0

classe de complexitat


La classe de complexitat TC0 és usada en complexitat de circuits. És la primera classe de la jerarquia de les classes TC.[1][2]

La classe TC0 conté tots els llenguatges que son decidibles per un circuit booleà amb profunditat constant i mida polinòmica, format només per portes AND, OR, NOT i majoria. Equivalentment, es poden usar portes de llindar enlloc de portes de majoria.

Aquesta classe conté problemes força importants, com el d'ordenar n nombres de n bits, multiplicar dos nombres de n bits, la divisió entera o reconèixer el llenguatge de Dyck amb dos tipus de parèntesis.

Relació amb d'altres classes modifica

Es pot relacionar la classe TC0 amb altres classes de circuits, incloent AC0 i NC¹:

 

També és conegut que:

 

Referències modifica

  1. Hesse, William; Allender, Eric; Mix Barrington, David A. «Uniform constant-depth threshold circuits for division and iterated multiplication». Journal of Computer and System Sciences, 65, 4, 2002-12, pàg. 695–716. DOI: 10.1016/s0022-0000(02)00025-9. ISSN: 0022-0000.
  2. Peter., Clote,. Boolean functions and computation models. Berlín: Springer, 2002. ISBN 3540594361.