wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

ac (494B)

      1 # AC
      2 
      3 "alternating" circuit class: ACi is the class of [formal_language] recognized by [boolean_circuit] of polynomial number of gates of unbounded [fan_in] and with depth O(log^i n)
      4 
      5 - [ac0]: constant depth
      6 - [ac1]: singly logarithmic depth
      7 
      8 This is like [nc] but:
      9 - with AC the gates have unbounded fan-in
     10 - with NC they have constant fan-in:
     11 
     12 Hence: NCi is included in ACi which is included in NCi+1 for all i
     13 
     14 Generalization: class [acc] where we allow [modulo_gate]
     15 
     16 Up: [circuit_classes]