文献

J-GLOBAL ID：202202230399052649   整理番号：22A0729477

VNP完全性と境界複雑性に関するノート【JST・京大機械翻訳】

A note on VNP-completeness and border complexity

著者 (2件)： Ikenmeyer Christian (University of Liverpool, United Kingdom) ,  Sanyal Abhiroop (Chennai Mathematical Institute, India)
資料名： Information Processing Letters  (Information Processing Letters)
巻： 176  ページ： Null  発行年： 2022年 
JST資料番号： E0513A  ISSN： 0020-0190  資料種別： 逐次刊行物 (A)
記事区分： 短報  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 1979年のValiantは,多項式のp-定義可能ファミリーの複雑性クラスVNPを導入し,p-投影として知られる縮小概念を定義し,そして,永久多項式とハミルトニアンサイクル多項式が,p-投影の下でVNP完全であることを立証した。2001年MulmuleyとSohoni(独立Buergiser)は,多項式の代数的複雑性の研究に対する境界複雑性の概念を導入した。この代数的機械モデルでは,正確な計算に代わって,近似が許される。これはVNPをトポロジー空間の構造に与えた。この短報では,VNP完全多項式の集合VNPCを研究した。補体VNP VNPCはVNPで高密度である。驚くべきことに,VNPCはVNPにおいて高密度であることも証明した。複雑性クラスVF,VBP,およびVPのための類似ステートメントを証明した。VNP Ψ VNPCの密度は,いくつかの異なる還元概念:p-投影,境界p-投影,c-還元,および境界c-還元に対して保持された。これらの削減の下で完全性概念の関係を比較し,対応する集合の大部分を分離した。Bringmann,Ikenmeyer,およびZuiddam((2018))によって,次数低減概念を導入した。本論文は,境界低減概念の最初の構造化研究である。Copyright 2022 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 位相空間 ,  *多項式 ,  補体 ,  近似法 ,  計算量 ,  計算理論 ,  力学モデル ,  集合 ,  *性質 ,  完全性
準シソーラス用語： 高密度 ,  複雑性 , 【Automatic Indexing@JST】

著者キーワード (5件)： 計算の理論 ,  計算の複雑さ ,  代数複雑性理論 ,  境界の複雑さ ,  還元

分類 (2件)： 計算理論  (JB02000A) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 境界 ,  複雑性 ,  ノート