文献

J-GLOBAL ID：202002260539178193   整理番号：20A1495331

コンパクト計量空間の定量的符号化と計算量理論【JST・京大機械翻訳】

Quantitative Coding and Complexity Theory of Compact Metric Spaces

著者 (2件)： Lim Donghyun (School of Computing, KAIST, Daejeon, Republic of Korea) ,  Ziegler Martin (School of Computing, KAIST, Daejeon, Republic of Korea)
資料名： Lecture Notes in Computer Science  (Lecture Notes in Computer Science)
巻： 12098  ページ： 205-214  発行年： 2020年 
JST資料番号： H0078D  ISSN： 0302-9743  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 計算問題の特定は,入力と出力のための符号化を必要とする:隣接行列としてグラフを符号化し,整数として文字,ビットストリングとして整数,そして,その逆である。そのような離散データに対して,実際の符号化は,通常,(多項式時間まで),すなわち,本質的には,直接的かつ/または複雑性-理論的である。しかし,連続データに関して,既に実数では,非常に異なる計算特性を有する様々な符号化を自然に示唆した。定性的計算可能性に関して,KreitzとWeihrauch(1985)は,無限二進シーケンスのCantor空間,いわゆる表現の上の「合理的」符号化のための重要な特性として許容性を同定した。(正確に),それらは,Kreitz-Weihrauch表現(高主)定理を適用して,連続実現者に関して関数の連続性を特徴づけた。同様に,定量的複雑性調査に適した表現のための精密化基準を同定した。より一般的なコンパクトな計量空間を持つ地上空間としてCantorを置き換えることにより,より高いタイプの複雑さを捉え,計算可能性における等値空間に類似した。Copyright Springer Nature Switzerland AG 2020 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 計算可能性 ,  実数 ,  *計算量理論 ,  精密化 ,  連続性
準シソーラス用語： 隣接行列 ,  複雑性 ,  多項式時間 , 【Automatic Indexing@JST】

分類 (1件)： 符号理論  (ND02030R)

タイトルに関連する用語 (5件)： コンパクト ,  計量 ,  定量 ,  符号化 ,  計算量理論