Sizes of Cohen-type forcing condition : Application to randomness and computational complexity

我们改进了下文中的主要定理。铃木敏夫，数理逻辑资料馆，vol .44（2005）第751-762页。将上述主要定理中的常数范数放宽为常数与范数的倍数。这个结果的总结可以在下面的研究报告中找到。M. Kumabe， T. Suzuki和T. Yamazaki，“强迫条件的真值表缩减和最小尺寸”，surikaisekikenkyuso -kokyuroku, vol. 1533(2007)，京都大学数学科学研究所。我们研究由并行连接的布尔决策树的拷贝定义的布尔函数。输入字符串由叶子给出，输出字符串由根给出。研究了这类布尔函数守恒的弱随机性性质。证明了该类布尔函数保持马丁-洛夫随机性的一个必要条件。必要条件是，对于每一个正整数r，给定的oracle在Dowd意义上是r-泛型的。我们将在接下来的会议报告中报告这一结果。“布尔决策树保留了哪些弱随机性性质？”，证明理论2007（2007年12月3-4日），东京都市大学。

We improve the main theorem of the following paper. Toshio Suzuki, Archive for Mathematical Logic, vcol.44 (2005) pp. 751-762. The constant norm in the main theorem of the above paper is relaxed to multiple of constant and the norm. Summary of this result may be found in the following research report. M. Kumabe, T Suzuki and T. Yamazaki, "Truth-table reductions and minimum sizes of forcing conditions", Surikaisekikenkyusho-kokyuroku, vol. 1533 (2007), Research Institute of Mathematical Sciences, Kyoto University.We study Boolean functions defined by copies of a Boolean decision tree connected in parallel. An input string is given to leaves, and an output string is given by roots. We investigate which kind of weak randomness property is conserved by this type of Boolean functions. We showed a necessary condition of Martin-Loef randomness is conserved by this type of Boolean functions. The necessary condition is that for every positive integer r, a give oracle is r-generic in the sense of Dowd. We report this result at the following conference talk. "Which weak-randomness property is preserved by Boolean decision trees?", Proof theory 2007 (2007 December 3-4), Tokyo Metropolitan-University.