Talk:AC (complexity)

From Wikipedia, the free encyclopedia
Jump to: navigation, search
WikiProject Mathematics (Rated Start-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:
Start Class
Low Priority
 Field: Discrete mathematics

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)