抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
クラスPPA-pは,pthievesによるNecklace分割の複雑性を捕えるための主要な候補であるので,これらのクラスはトポロジー的性質の完全な問題を有することは知られておらず,Necklace分割問題の複雑性を沈降するのにいかなる進展も妨げるというわけではないので,これらのクラスは注目を浴びている。”そのクラス”は,最近,注目を浴びている。”これらのクラスは,ptievesによるNecklace分割の複雑性を捉えるのに,主要な候補であったため,これらのクラスは,トポロジー的性質の完全な問題を有することが知られていなかった。反対に,トポロジー問題は,PPADとPPAの完全性結果を得るために,Nash均衡[Daskalakis et al.,2009年,Chen et al.,2009b],およびNecklace分割のPPA完全性を,2つのチベス[Filoss-RatskasとGoldberg,2019]で発見するのに重要である。本論文では,クラスPPA-pの最初のトポロジー特性化を提供した。第1に,p-多角形-Tuckerと呼ばれるTuckerのLemmaの簡単な一般化,並びに関連するBorsuk-Ulm型定理,p-多角形-Borsuk-Ulm,がPPA-p-完全である,という計算問題を示した。次に,よく知られたBSS定理[Barany et al.,1981]および関連するBSS-Tucker問題の計算バージョンがPPA-p完全であることを示した。最後に,PPA-p完全であると証明するTuckerのLemma(Z_p-star-Tucker)の異なる一般化を用いて,p-thief Necklace分裂がPPA-pにあることを証明した。この後者の結果は,Necklace分割定理の新しい組合せ証明を与え,Meunier[2014]以外のこの性質の唯一の証明である。FreundとTodd[1981]によるTuckerの補助定理の標準的な組合せ証明の自然な一般化であるTuckerの補助定理のZ_p-バージョンの新しい組合せ証明を通して,著者らの格納容器結果のすべてを得た。この新しい証明技術は,独立の関心事である。【JST・京大機械翻訳】
