Talk:TC0

Wrong statement[edit]

The statement "uniform ${\mbox{TC}}^{0}\subsetneq {\mbox{PP}}$ " must be wrong, because ${\mbox{TC}}^{0}\subseteq {\mbox{NC}}^{1}\subseteq {\mbox{P}}\subseteq {\mbox{NP}}\subseteq {\mbox{PP}}$ . The first inclusion is stated in this article, the second one in that about NC¹, the third one in that about NP, and the fourth one in that about PP. --Tillmo (talk) 04:14, 6 April 2013 (UTC)[reply]

I don't see that it must be wrong: it says that uniform TC0 is contained in but not equal to PP and this is consistent with the chain of inclusions you give. It is also reasonably sourced. Deltahedron (talk) 06:27, 6 April 2013 (UTC)[reply]

Make sure you note the difference between the statements

{\mbox{TC}}^{0}\subsetneq {\mbox{PP}}

and

{\mbox{TC}}^{0}\nsubseteq {\mbox{PP}}

. The first statement (which is correct, and in the article) says that TC0 is contained in and not equal to PP; in other words, TC0 is "strictly contained in" PP. The second statement would be "TC0 is not contained in PP", and is incorrect, as you've noted. Some authors would write the equation in the article as

{\mbox{TC}}^{0}\subset {\mbox{PP}}

, but that notation is used ambiguously (see Subset#The_symbols_.E2.8A.82_and_.E2.8A.83). -- Creidieki 20:07, 6 April 2013 (UTC)

you are right, I confused the two. --Tillmo (talk) 09:44, 7 April 2013 (UTC)[reply]