実験計算量理論の確立と展開

实验复杂性理论的建立与发展

• 批准号: 18K11152
• 负责人: 天野 一幸
• 金额: $ 2.75万
• 依托单位: Gunma University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K11152/
• 关键词: 計算複雑性理論; 整数複雑さ; 下界; 多項式しきい値関数; 論理関数; 計算複雑さ; 計算機援用; 離散構造; しきい値回路; 計算量理論; 充足可能性問題; 数理計画; しきい値論理回路; 論理回路; 実験数学; 整数計画; 多数決関数; 閾値回路

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

这项研究使用计算机辅助方法，专门对计算复杂性进行分析，这是理论计算机科学领域的挑战性问题之一。今年，我们在以下两个方面取得了一定成效。 1.当给定的自然数用数字1、加法、乘法和括号表示时，使用数字1的最少次数称为该数字的整数复杂度。尽管这个问题很简单，由 Mahler 和 Popken 在 20 世纪 50 年代提出，但找到良好的上限和下界多年来仍然是一个未解决的问题。在这项研究中，我们关注的事实是，迄今为止已知的最佳上限是基于二元表示，最佳下界是基于三元表示，并且我们提出了一种混合二元-三元表示，可用于顺序，并使用这种表示法分析了整数复杂度。结果，我们成功地改进了众所周知的平均复杂度上限，并获得了有关整数复杂度分布的新知识。结果在国际会议 ISAAC2022 上公布。 2.我们分析了多项式阈值表示的复杂性，它是逻辑函数的重要表示方法之一。特别是，对于以这种格式表示称为 ODD-MAXBIT 函数的逻辑函数时找到系数和的下界的问题，我们成功地证明了一个几乎与已知的上界相匹配的下界。这解决了一个存在了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

On the Minimum Number of Pieces for Two-Dimensional Anti-Slide Using T-Tetrominoes

T形四联板二维防滑的最小块数研究

• DOI: 10.1587/transinf.2020fcp0007
• 发表时间: 2021
• 期刊: IEICE Transactions on Information and Systems
• 影响因子: 0.7
• 作者: KIMURA Kento;AMANO Kazuyuki;ARAKI Tetsuya
• 通讯作者: ARAKI Tetsuya

Depth Two Majority Circuits for Majority and List Expanders

用于多数和列表扩展器的深度两个多数电路

• DOI: 10.4230/lipics.mfcs.2018.81
• 发表时间: 2018
• 期刊: LIPIcs (Leibniz International Proceedings in Informatics)
• 作者: H. A. Akitaya;E. D. Demaine;T. Horiyama;T. C. Hull;J. S. Ku;T. Tachi,;Kazuyuki Amano
• 通讯作者: Kazuyuki Amano

数理計画を用いた閾値回路の計算複雑さの解析

用数学规划分析阈值电路的计算复杂度

• 发表时间: 2020
• 作者: M. de Brecht;天野 一幸
• 通讯作者: 天野 一幸

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

骑士交换谜题的泛化研究

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