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.

我们改善了以下论文的主要定理。 Toshio Suzuki，《数学逻辑档案》，VCOL.44（2005），第751-762页。上文主定理中的恒定规范放松到恒定和规范的倍数。该结果的摘要可以在以下研究报告中找到。 M. Kumabe，T Suzuki和T. Yamazaki，“真相表的减少和最小尺寸强迫条件”，Surikaisekikikenkyusho-Kokyuroku，第1卷。 1533（2007），京都大学数学科学研究所。我们研究布尔功能由并行相关的布尔决策树的副本定义。给叶子给出一个输入字符串，并由根部给出一个输出字符串。我们研究了这种类型的布尔函数保留了哪种弱随机性特性。我们表明，通过这种布尔函数保存了马丁 - 石油随机性的必要条件。必要的条件是，对于每个正整数r，就Dowd的意义上，ives oracle都是r-generic。我们在以下会议演讲中报告了此结果。 “布尔决策树保留了哪些弱者的财产？”

项目成果

Truth-table reductions and minimum sizes of forcing conditions (preliminary draft)

真值表缩减和强制条件的最小尺寸（初步草案）

• 发表时间: 2007
• 期刊: 数理解析研究所講究録 1533
• 作者: M.Kumabe;T.Suzuki;T.Yamazaki
• 通讯作者: T.Yamazaki

Logarithmic truth-table reductions and minimum sizes of forcing conditions

对数真值表缩减和强制条件的最小尺寸

• 发表时间: 2005
• 期刊: 京都大学数理解析研究所講究録 1442
• 作者: M.Kumabe(T Suzuki;T.Yamazakiと連名)
• 通讯作者: T.Yamazakiと連名)

Truth-table reduction and minimum sizes of forcing conditions

真值表缩减和强制条件的最小尺寸

• 发表时间: 2006
• 作者: 鈴木 登志雄(隈部 正博;山崎 武と連名)
• 通讯作者: 山崎 武と連名)

ゲーデルと20世紀の論地学(1) ゲーデルの20世紀

哥德尔与20世纪地质学（一）哥德尔的20世纪

• 发表时间: 2007
• 作者: 田中一之 編;田中一之;田中尚夫;鈴木登志雄 ほか著
• 通讯作者: 鈴木登志雄 ほか著

算術的フォーシングとフォーシング条件:クエリー記号付きプール式・計算量およびランダム性との関連

算术强制和强制条件：池公式与查询符号、计算复杂度和随机性之间的关系

• 发表时间: 2006
• 作者: Tomoyuki;Yamakami (Toshio;Suzuki);H.Matsumoto;鈴木 登志雄
• 通讯作者: 鈴木 登志雄