权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

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

科恩型强迫条件的大小：在随机性和计算复杂性中的应用

基本信息

批准号：
17540131
负责人：
SUZUKI Toshio
金额：
$ 2.16万
依托单位：
Tokyo Metropolitan University (2006-2007)Osaka Prefecture University (2005)
依托单位国家：
日本
项目类别：
Grant-in-Aid for Scientific Research (C)
财政年份：
2005
资助国家：
日本
起止时间：
2005 至 2007
项目状态：
已结题

来源：
https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17540131/
关键词：
mathematical logic foundation of computer sciences algorithm randomness random number

项目摘要

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.

我们改进了文[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日），东京都立大学。