On the Maximum Tolerable Noise for Reliable Computation by Formulas
ID
TR-95-20
Publishing date
September 1995
Length
16 pages
Abstract
It is shown that if a formula is constructed from noisy 2-input NAND gates, with each gate failing independently with probability e, then reliable computation can or cannot take place according as e is less than or greater than e_0 = (3-sqrt(7))/4 = 0.08856....