Complexitat de circuits: diferència entre les revisions
Contingut suprimit Contingut afegit
m neteja i estandardització de codi |
m Bibliografia |
||
Línia 34:
La classe uniforme TC<sup>0</sup> està estrictament continguda dins de PP.<ref>{{Ref-publicació|cognom=Allender|nom=Eric|article=Circuit complexity before the dawn of the new millennium|publicació=Technical Report|llengua=en|url=https://link.springer.com/chapter/10.1007/3-540-62034-6_33|data=1996-12-18|editorial=Springer, Berlin, Heidelberg|pàgines=1–18|doi=10.1007/3-540-62034-6_33}}</ref>
Les classes de complexitat [[S2P (Complexitat)|S{{su|p=P|b=2}}]], [[PP (complexitat)|PP]] i [[MA (Complexitat)|MA/1]] no estan dins de MIDA(n<sup>k</sup>) per qualsevol constant ''k''.<ref>{{Ref-publicació|article=A note on the circuit complexity of PP|publicació=Theoretical Computer Science|llengua=en|url=https://www.sciencedirect.com/science/article/pii/S0304397505004809|volum=347|exemplar=1-2|data=2005-11-30|pàgines=415–418|doi=10.1016/j.tcs.2005.07.032|issn=0304-3975}}</ref><ref>{{Ref-publicació|cognom=Santhanam|nom=Rahul|article=Circuit Lower Bounds for Merlin-Arthur Classes|publicació=STOC 2007: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing|url=http://doi.acm.org/10.1145/1250790.1250832|data=2007|editorial=ACM|lloc=
Se sap que [[NEXPTIME|NEXP]] <math>\not \subseteq
| |||