Computational Complexity of Minimum Description Size Problems

最小描述大小问题的计算复杂度

• 批准号: 18H04090
• 负责人: Watanabe Osamu
• 金额: $ 24.63万
• 依托单位: Tokyo Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (A)
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2022-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18H04090/
• 关键词: 計算複雑度理論; 最小記述量計算問題; P≠NP予想; メタ計算; 最悪時時間計算量; 平均時時間計算量; 計算論的学習理論; 計算論的暗号理論; 最小記述量; 平均時計算複雑度; 学習計算困難さ; 一方向関数; 最小記述量計算; 多項式時間階層; 平均時計算困難性; 計算論的暗号; PAC学習困難性; 機械学習; Ｐ≠ＮＰ予想; 平均時計算量; 学習可能性; 情報セキュリティ; 情報セキュリティ技術; 最小回路サイズ問題; 回路計算量; 質問計算量

项目成果

An Improved Fixed-Parameter Algorithm for Max-Cut Parameterized by Crossing Number

一种改进的交叉数参数化最大割定参数算法

• 发表时间: 2019
• 作者: Yasuaki Kobayashi;Yusuke Kobayashi;Shuichi Miyazaki and Suguru Tamaki
• 通讯作者: Shuichi Miyazaki and Suguru Tamaki

On XOR Lemmas for the Weight of Polynomial Threshold Functions

多项式阈值函数权重的异或引理

• DOI: 10.1016/j.ic.2019.104439
• 发表时间: 2019
• 期刊: Information and Computation
• 影响因子: 1
• 作者: Gima Tatsuya;Hanaka Tesshu;Kiyomi Masashi;Kobayashi Yasuaki;Otachi Yota;Kazuyuki Amano and Shoma Tate
• 通讯作者: Kazuyuki Amano and Shoma Tate

On the Number of p4-tilings by an N-omino

关于 N-omino 的 p4-平铺数量

• DOI: 10.1142/s0218195919400016
• 发表时间: 2019
• 期刊: International Journal of Computational Geometry and Applications (IJCGA)
• 作者: Yoshiki Nakamura;Kazuyuki Asada;Naoki Kobayashi;Ryoma Sin'ya;Takeshi Tsukada;金澤慶明，西田直樹，酒井正彦;Kazuyuki Amano and Yoshinobu Haruyama
• 通讯作者: Kazuyuki Amano and Yoshinobu Haruyama

A Simple and Fast Algorithm for Computing the <i>N</i>-th Term of a Linearly Recurrent Sequence

计算线性循环序列第N项的简单快速算法

• DOI: 10.1137/1.9781611976496.14
• 发表时间: 2021
• 期刊: in Proc. SODA 2021
• 作者: 平賀 大一;秦 俊陽;松井 崇;下田 亮;岡本 正洋;征矢 英昭;Bostan Alin and Mori Ryuhei
• 通讯作者: Bostan Alin and Mori Ryuhei

An improvement of the algorithm of Hertli for the Unique 3SAT problem

针对Unique 3SAT问题的Hertli算法的改进

• 发表时间: 2019
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Tong Qin;Osamu Watanabe
• 通讯作者: Osamu Watanabe