Summary: Long Random Linear Programs

• Above a threshold, distribution of performance is independent of length

  
  

• Threshold depends on instruction set $\approx -1/\log \vert \lambda_{2} \vert$
  (where $\lambda_{2}$ is the magnitude of the 2nd largest eigenvalue)

• If instruction set is symmetric, any output is equally likely
  If tests are independent, chance of long random solution $=2^{- \vert\mbox{test set}\vert}$

• Symmetric problems (e.g. multiplexor, parity) chance of long random solution $\le 2^{- \vert\mbox{test set}\vert}$
  Tolerable degree of asymmetry in machine falls as $O\left({\vert\mbox{test set}\vert^{-1/2}}\right)$

  
  

• The number of solutions grows exponentially with size.

  
  

• Chance of finding a general solution is exponentially small.