Abstract:
We consider the realization of Boolean functions by nonbranching programs with conditional stop-operators in an arbitrary complete finite basis. We assume that conditional stop-operators are absolutely reliable, while all functional operators are prone to output inverse failures independently of each other with probability $\varepsilon$ from the interval (0,1/2). We prove that any Boolean function is realizable by a nonbranching program with unreliability $\varepsilon+81\varepsilon^2$ for all $\varepsilon\in(0,1/960]$.