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

我们改进了文[1]的主要定理。Toshio Suzuki，Archive for Mathematical Logic，vcol.44（2005）pp. 751-762.将上述主要定理中的常数范数放宽为常数与范数的倍数。这一结果的摘要可在以下研究报告中找到。M. Kumabe，T Suzuki和T. Yamazaki，“Truth-table reductions and minimum sizes of forcing conditions”，Surikaisekikenkyusho-kokyuroku，vol.1533（2007），Research Institute of Mathematical Sciences，京都大学.我们研究由并行连接的布尔决策树的副本定义的布尔函数.一个输入字符串被赋予叶子，一个输出字符串被赋予根。我们研究了这类布尔函数的弱随机性是什么性质。我们证明了这类布尔函数的Martin-Loef随机性是守恒的一个必要条件。必要条件是对每一个正整数r，给定的预言机在Dowd意义下是r-泛型的。我们在下面的会议上报告这一结果。“布尔决策树保留了哪种弱随机性属性？”，Proof theory 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.