次元2におけるPL幾何学的カテゴリー計算のNP困難性【JST・京大機械翻訳】

Skotnica Michael; Tancer Martin

プレプリント

J-GLOBAL ID：202202201349548330 整理番号：22P0340896

次元2におけるPL幾何学的カテゴリー計算のNP困難性【JST・京大機械翻訳】

NP-hardness of computing PL geometric category in dimension 2

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (2件)： ,
資料名：
発行年： 2022年04月29日プレプリントサーバーでの情報更新日： 2023年03月30日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

多面体PのPL幾何学的カテゴリーは,plgcat(P)を示し,Lusternik-Schnielmannカテゴリーに対する自然な上界を提供し,Pを覆っているPのPL崩壊可能サブ多面体の最小数として定義される。次元2において,PL幾何学的カテゴリーは,ほとんど3であった。plgcat(P)=1で2-多面体Pを特性化/認識することは容易である。Borghiniは,plgcat(P)=2を有する2-多面体の部分的特性化を提供した。plgcat(P)≦2がNP困難であることを示すことにより,その結果を補完した。したがって,少なくともアルゴリズム的意味において,部分的特性化よりはるかに多くは期待するべきではない。この還元は,2次元多面体Pがシェル可能な細分化を満たすという観察に基づき,Gaooc,Pat’akov’a,TancerおよびWagnerの還元の(非自明な)修正が,2錯体のシェル性がNP困難であることを示す観察に基づいている。【JST・京大機械翻訳】

, , , , ,
, , 【Automatic Indexing@JST】

炭素とその化合物

, , , , ,

前のページに戻る