Talk:TC0

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Stub-class, Low-priority)
WikiProject Mathematics
This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of Mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
Mathematics rating:
Stub Class
Low Priority
 Field: Discrete mathematics

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 NC1, the third one in that about NP, and the fourth one in that about PP. --Tillmo (talk) 04:14, 6 April 2013 (UTC)

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