The Boolean functions computed by random Boolean formulas or how to grow the right function. (English) Zbl 1083.94024
Summary: We characterize growth processes (probabilistic amplification) by their initial conditions to derive conditions under which results such as L. G. Valiant [J. Algorithms 5, 363–366 (1984; Zbl 0554.94017)] hold. We completely characterize growth processes that use linear connectives and generalize P. Savický’s [Discrete Math. 83, 95–103 (1990; Zbl 0703.06006)] analysis to characterize growth processes that use monotone connectives. Additionally, we obtain explicit bounds on the convergence rates of several growth processes, including the growth process studied in Savický.
MSC:
| 94C10 | Switching theory, application of Boolean algebra; Boolean functions (MSC2010) |
| 68Q25 | Analysis of algorithms and problem complexity |
| 03B05 | Classical propositional logic |
Keywords:
computational and structural complexity; growth processes; probabilistic amplification; random Boolean functionsReferences:
| [1] | Andreev, Sov Math Dokl 29 pp 32– (1984) |
| [2] | Modular functions and Dirichlet series in number theory, 2nd edition, Springer, New York, 1997. |
| [3] | On some relationships between monotone and nonmonotone circuit complexity, Technical report, Department of Computer Science, University of Toronto, Canada, Toronto, Canada, 1982. |
| [4] | Amplification of probabilistic Boolean formulas, Proc 26th Annu IEEE Symp Foundations of Computer Science, October, 1985, pp. 20-29. |
| [5] | ” Amplification of probabilistic Boolean formulasm,” Advances in computing research 5: Randomness and computation, 28-45. (Editor), JAI Press, Greenwich, CT, 1989. |
| [6] | Dubiner, SIAM J Comput 26 pp 15– (1997) |
| [7] | Glagolev, Problemy Kibernetiki 19 pp 75– (1967) |
| [8] | ” A theorem of finite sets,” Theory of graphs, 187-207. (Editors), Akademia Kiado, Budapest, 1968. |
| [9] | Korshunov, Problemy Kibernetiki 38 pp 5– (1980) |
| [10] | ” The optimal number of simplices in a complex,” Mathematical optimization techniques, 251-268. University of California Press, Berkeley, California, 1963. |
| [11] | Kurdyavcev, Sov Math Dokl 1 pp 537– (1960) |
| [12] | Kurdyavcev, Sov Math Dokl 1 pp 146– (1960) |
| [13] | Lefmann, Random Structures Algorithms 10 pp 337– (1997) |
| [14] | Lupanov, Problemy Kibernetiki 6 pp 5– (1961) |
| [15] | Moore, J Franklin Inst 262 pp 191– (1956) |
| [16] | Razborov, Voprosy Kibernetiky, USSR 134 pp 149– (1988) |
| [17] | Riordan, J Math & Phys 21 pp 83– (1942) · doi:10.1002/sapm194221183 |
| [18] | Sapozhenko, Diskret Mat 1 pp 110– (1989) |
| [19] | Savický, Discrete Math 83 pp 95– (1990) |
| [20] | Savický, Discrete Math 147 pp 211– (1995) |
| [21] | Savický, Random Structures Algorithms 6 pp 407– (1995) |
| [22] | Savický, Combinat Probab Comput 7 pp 451– (1998) |
| [23] | Shannon, AIEE Trans 57 pp 713– (1938) |
| [24] | Valiant, J Algorithms 5 pp 363– (1984) |
| [25] | ” Probabilistic logics and the synthesis of reliable organisms from unreliable components,” Automata studies, 43-98. (Editors), Princeton University Press, Princeton, NJ, 1956. |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
