12 - Circuits

• circuits are a simplified mdoel of the silicon chip -> can be sued to copmute any logical function and have their own cost parameters : size + depth
• processing units

  efficient general-purpose hardware
• Logical circuits are represented by boxes == gate

  A) not

  B) !x0

  
• Terminology

  A) fan-in

  B) fan-out

  
• Circuit (informal)

  A) network of directed wires

  B) and or not

  C) n

  D) m

  
• A logical circuit is a directed acyclic graph.
• input length = number of input nodes

  output length = number of output nodes
• size of a circuit

  total number of gates
• depth of a circuit

  length of the longest directed path
• depth only makes sense if the underlying graph does not contain any cycles
• circuit size equals TM runtime
• circuit parity of sum has a depth of log_2(n) where n is the number of input bits
• s(XOR) = 4 , d(XOR) = 3
• circuit depth equals parellize runtime
• ParityOfSum is a regular language, we can always decide membership with a DFA. Runtime of a DFA is always equal to input length n .
• logical functions can always be represented as circuits
• let f be a logical function with n input bits and m output bits. Then

  A) n

  B) size

  C) depth

  D) mn2^n

  
• conversion into n-CNF is extremely useful when one attempts to design circuits with short circuit depths.
• if we have a k-CNF with l clauses. Then a circuits

  
  

  size s(C) =< 2kl-1 = O(kl)

  depth s(C) =< [log_2(k)] + [log_2(l)]+1 = O(log(kl))
• If we have m circuits :

  size(C) = $\sum_{i=1}^m s_i$ =< mn2^(n+1) = O(mn2^n)

  depth(C) = max_i d_i =< n+[log_2(n)]+1 = O(n)
• encode the 4 tape symbols in

  • 0 = 00
  • empty square = 01
  • roadblock = 10
  • 1 = 11
• Translate this into to a transition function :

  Q x tape alphabet -> Q x tape alphabet x {L,R}

  (q,a) -> (p,b,D)

  
• the size of the circuit dpeends on the number of TM states (Q), S(C) = O(1)
• a zig-zag TM M processes length-n inputs x by repreatedly zig-zaggin across a fixed section of S(n) tape squars.
• zigzag, once it hits the #-symbol it reverse direction and moves bag again.
• Tpae movements of zig-zag TMs are extremely regular and independant from the content of the actual input string.
• Zig-zag TMs

  A) simulate

  B) T(n)^2

  C) T(n)

  
• Representing TMs as circuits

  A) circuit

  B) zero

  C) forall

  
• Circuits can only process inputs of fixed length n (nonuniform computation). This is in stark contrast to TMs which can process inputs of arbitrary length (uniform computation).