不動点定理に基づく計算量クラスの細分化に関する研究

研究計画当初、本研究課題では計算量クラスTFNPに属するふたつの計算量クラスEOPLとCLSの関係を明らかにすることを掲げていた。しかし、これらふたつの計算量クラスの関係については、別の研究者たちが[Goos et al., CCC, 2022]で証明を与えた。それに伴い、本年度は計算量クラスTFNPに対する理解を深めるため、応用的な計算問題の複雑さを解明する、応用的な研究を重点的に行った。計算量クラスTFNP（および、その部分クラスたち）は、他の一般的な計算量クラスと異なり、計算に必要な時間や空間といったコストを基準に分類されているものではない。そのため、計算量クラスの複雑さを捉えるために、具体的な完全問題の実例を探り、どのような性質が計算問題を複雑にするのか、あるいは簡単にするのかを調査することが重要である。欠かせない。本研究課題においても、応用的な計算問題としてゲームのNash均衡計算問題を中心に調査を行った。純Nash均衡を常にもつ離散選好ゲームはグラフの次数が定数であっても、純Nash均衡を計算することはPLS完全である[Lolakapuri et al., IJICAI, 2019]。本研究では、離散選好ゲームについて、効率的なアルゴリズムが存在する特殊ケースを探る研究を行い、４次以上であってもある条件を満たせば、多項式時間で計算可能であることを示した。利得行列が0と1で形成される2人ゲーム上の一様Nash均衡計算問題では、ゲームの平面性が計算複雑性に影響を与えることが知られている[Bonifaci et al, TCS, 2008], [Addario-Berry et al., JGAA, 2007]。本研究において、利得行列の2値性もまた一様Nash均衡の計算困難性に影響を与えることを明らかにした。

研究計画当初、本研究課題では計算量クラスTFNPに属するふたつの計算量クラスEOPLとCLSの関係を明らかにすることを掲げていた。しかし、これらふたつの計算量クラスの関係については、別の研究者たちが[Goos et al., CCC, 2022]で証明を与えた。それに伴い、本年度は計算量クラスTFNPに対する理解を深めるため、応用的な計算問題の複雑さを解明する、応用的な研究を重点的に行った。計算量クラスTFNP（および、その部分クラスたち）は、他の一般的な計算量クラスと異なり、計算に必要な時間や空間といったコストを基準に分類されているものではない。そのため、計算量クラスの複雑さを捉えるために、具体的な完全問題の実例を探り、どのような性質が計算問題を複雑にするのか、あるいは簡単にするのかを調査することが重要である。欠かせない。本研究課題においても、応用的な計算問題としてゲームのNash均衡計算問題を中心に調査を行った。純Nash均衡を常にもつ離散選好ゲームはグラフの次数が定数であっても、純Nash均衡を計算することはPLS完全である[Lolakapuri et al., IJICAI, 2019]。本研究では、離散選好ゲームについて、効率的なアルゴリズムが存在する特殊ケースを探る研究を行い、４次以上であってもある条件を満たせば、多項式時間で計算可能であることを示した。利得行列が0と1で形成される2人ゲーム上の一様Nash均衡計算問題では、ゲームの平面性が計算複雑性に影響を与えることが知られている[Bonifaci et al, TCS, 2008], [Addario-Berry et al., JGAA, 2007]。本研究において、利得行列の2値性もまた一様Nash均衡の計算困難性に影響を与えることを明らかにした。