An Analysis of Memory Space Usage by Algorithms Solving NL Search Problems

解决NL搜索问题的算法对内存空间使用的分析

• 批准号: 16K00013
• 负责人: YAMAKAMI TOMOYUKI
• 金额: $ 2.83万
• 依托单位: University of Fukui
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2016
• 资助国家: 日本
• 起止时间: 2016-04-01 至 2019-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-16K00013/
• 关键词: 計算量理論; 使用メモリ領域量; アルゴリズムの効率; 線形領域仮説; オンラインアルゴリズム; 弱線形メモリ領域還元; 線形メモリ領域仮説; 弱線形メモリ領域計算; オートマトン; 内部状態数; 計算モデル; トポロジカルオートマトン; アルゴリズム; 非決定性対数領域計算; NL 最適化問題; NL 探索問題; 決定性アルゴリズムの効率; 巨大ベータ処理; メモリ領域; 半線形領域計算量; パラメタ化; 有向グラフ経路探索問題; 論理式充足判定問題; 線形

项目成果

Tomoyuki Yamakami Homepage

山上智之主页

State complexity characterizations of parameterized degree-bounded graph connectivity, sub-linear space computation, and the linear space hypothesis

参数化有界图连通性、次线性空间计算和线性空间假设的状态复杂性表征

• DOI: 10.1016/j.tcs.2019.09.006
• 发表时间: 2019
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Henning Fernau;Petra Wolf;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

The 2CNF Boolean formula satisfiability problem and the linear space hypothesis

2CNF布尔公式可满足性问题和线性空间假设

• DOI: 10.4230/lipics.mfcs.2017.6
• 发表时间: 2017
• 期刊: Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017), Leibniz International Proceedings in Informatics (LIPIcs)
• 作者: Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

Non-uniform state complexity of quantum finite automata and quantum polynomial-time logarithmic-space computation with quantum advice -- (preliminary report) --

量子有限自动机的非均匀状态复杂性和量子多项式时间对数空间计算与量子建议——（初步报告）——

• 发表时间: 2018
• 作者: Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami

Parameterized graph connectivity and polynomial-time sub-linear-space short reductions (preliminary report)

参数化图连通性和多项式时间子线性空间短约简（初步报告）

• DOI: 10.1007/978-3-319-67089-8_13
• 发表时间: 2017
• 期刊: Proceedings of the 11th International Workshop on Reachability Problems (RP 2017), Lecture Notes in Computer Science, Springer-Verlag
• 作者: Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami;Tomoyuki Yamakami
• 通讯作者: Tomoyuki Yamakami