「計算」の視点から見る数学的難問

从“计算”的角度看数学难题

• 批准号: 21K19758
• 负责人: 天野 一幸
• 金额: $ 3.24万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Challenging Research (Exploratory)
• 财政年份: 2021
• 资助国家: 日本
• 起止时间: 2021-07-09 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-21K19758/
• 关键词: 計算量理論; 整数複雑さ; 論理関数; 下界; 計算機援用; 計算複雑さ; P vs. NP問題; 離散構造; コラッツ予想; 充足可能性問題; P≠NP予想

本研究は，数学分野において長く未解決となっている様々な難問を，「計算」の視点から捉え直すことで，その困難さを解明し，あるいは，解決への糸口を得ようとするものである．これへ向けて，今年度は，特に以下の２点について成果を得ることができた．１．与えられた自然数を，数値の1と，加算，乗算，および，括弧を任意に用いて表現するときの，数値1の使用回数の最小値を，その数の整数複雑さと呼ぶ．1950年代に提唱されたこの問題は，そのシンプルさにも関わらず，良い上界，あるいは，下界を求めることは長年の未解決問題となっている．本研究では，これまで知られる最良の上界と下界が，それぞれ，2進数表現と3進数表現を元にしていることに着目し，2進と3進を任意の順番で使用できるとする，混合2-3進数表現を提案し，この表現を用いた整数複雑さについて解析を行った．その結果，平均的複雑さに対する，これまで知られる最良の上界の改良や，整数複雑さの分布についての新たな知見を得ることに成功した．この結果は，国際会議ISAAC2022において発表を行った．２．論理関数の重要な表現手法の一つである，多項式しきい値表現の複雑さに関する解析を行った．特に，ODD-MAXBIT関数と呼ばれる論理関数を，この形式で表現したときの，係数の絶対値の和に対する下界を求める問題に対して，既知の最良の上界とほぼマッチする下界を証明することに成功した．これは，20年来の未解決問題を解決したものである．証明には，ランダム割り当てと，論理関数の自己帰着性を巧妙に組み合わせた手法を用いており，より広く決定リストの表現長の解明への発展も期待できる．この結果は，電子情報通信学会論文誌に掲載された．これらに加えて，最疎充填問題等いくつかの離散数理的問題に対して興味深い進展が得られるなど，本研究の目的の達成に向けて重要な進展を得ることができた．

这项研究旨在阐明困难并找到解决从“计算”的角度解决数学领域未解决的各种困难问题的线索。对于今年，我们能够在以下两个点中实现结果：1。当使用数字1的数字1表示给定的自然数量时，加法，乘法和括号时，使用数量的数量次数的最小次数称为该数字的无数次数。尽管它很简单，但在1950年代提出的这个问题长期以来一直是寻求良好上边界的尚未解决的问题。在这项研究中，我们集中于以下事实：最著名的上限和下限分别基于二元和三元表示，并提出了混合的二进制内部表示，其中可以按任何顺序使用二进制和三元，并使用此表达式分析了整数复杂性。结果，我们成功地获得了有关平均复杂性和整数复杂性分布的最著名的新见解。这些结果在国际会议ISAAC2022。2中介绍。我们分析了多项式阈值表达式的复杂性，这是逻辑函数的重要表达方法之一。特别是，当以这种形式表达一个称为奇数最大功能的逻辑函数时，我们成功地证明了与最知名的上限匹配的下限几乎与上限匹配。这解决了一个尚未解决的问题已有20年了。该证明使用一种将随机分配与逻辑函数的自定义结合在一起的技术，预计它将得到更广泛的开发，以阐明决策列表的表达长度。结果发表在电子，信息和传播工程师研究所杂志上。除此之外，我们还取得了一些有趣的进步，以实现这项研究的目标，例如稀疏的填充问题。

项目成果

On the Size of Depth-Two Threshold Circuits for the Inner Product Mod 2 Function

• DOI: 10.1007/978-3-030-40608-0_16
• 发表时间: 2020-01-07
• 期刊: Language and Automata Theory and Applications
• 作者: Amano K

パズル「しろなべ」の計算複雑性

“Shironabe”难题的计算复杂性

• 发表时间: 2023
• 作者: 篠原 広佑;荒木 徹也;天野 一幸
• 通讯作者: 天野 一幸

Lower Bounds on the PTF Weight of ODD-MAXBIT Function

ODD-MAXBIT 函数的 PTF 权重下界

• DOI: 10.1587/transfun.2022dml0003
• 发表时间: 2023
• 期刊: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences
• 作者: AMANO Kazuyuki

Knights Exchange Puzzleの一般化に関する研究

骑士交换谜题的泛化研究

• 发表时间: 2023
• 作者: Masashi Tsuchida;Fukuhito Ooshita;and Michiko Inoue;田島 大也，天野 一幸
• 通讯作者: 田島 大也，天野 一幸

1次元セルオートマトンのルール30の解析

一维元胞自动机规则30分析

• 发表时间: 2023
• 作者: 近藤和希;関川浩;西江一志，西田直樹，酒井正彦;内田 明良，天野 一幸
• 通讯作者: 内田 明良，天野 一幸