Talk:AC (complexity)
Add topic | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
2nd sentence confusing.
[edit]Earlier text reads:
Each class, ACi, consists of the languages recognized by Boolean circuits with unlimited-fanin AND gates and OR gates, using depth O(login) and a polynomial number of gates.
I changed it to:
Each class, ACi, consists of the languages recognized by unlimited-fanin Boolean circuits with depth O(login) and a polynomial number of AND and OR gates.
With new links for 'formal language', 'fanin', and 'polynomial'.
I changed 'unlimited-fanin AND gates' because an AND gate has only two inputs... rather the circuit as a whole might have unlimited inputs, but not individual gates. Same with 'depth 0(login)', which seems to apply better to the plural noun 'circuits' more than it does to 'gates'.
While I believe the new text is clearer, an editor more familiar with the topic should please verify that the revision is not less accurate.
Finally, why is this particular complexity class hierarchy called AC? The first thing folks want to know about acronyms is "what do the letters stand for"? --AC 20:56, 24 August 2007 (UTC)
- After some research, moved 'fanin' back to 'gates'. --AC 21:07, 24 August 2007 (UTC)