一般化された剰余型計算量クラスの計算量について

スポンサーリンク

概要

• 論文の詳細を見る

• これまでに計数計算量クラスの一種として#P関数の値の整数定数p【greater than or equal】2を法とする剰余に基づいて言語の受理条件を設定した計算量クラス(剰余型計算量クラス)の研究が行われている.本稿では,剰余の法を入力に依存する関数によって与える場合にこのクラスを拡張しその計算量を研究する.主に,このクラスが#Pと多項式時間等価であること,およびこのクラスがAmpMPに多項式時間還元可能であることを示す.本研究の背景にはより多くの整数論上の知識を計算量理論研究に役立てることが目標としてあり,本研究はその一つの試みである.

• 社団法人電子情報通信学会の論文
• 1993-04-23

著者

• ケブラー ヨハネス

  ウルム大学理論情報科学教室

• 戸田 誠之助

  電気通信大学情報工学科

• 戸田 誠之助

  電気通信大学

関連論文

• 敷居値関数と通信複雑度について
• グラフの彩色和の近似について
• 一般化された剰余型計算量クラスの計算量について
• VLSIモデルへのグラフの埋め込みについて(計算機構に関する数学的基礎理論とその応用)
• 最小切点集合を求めるための$O(N^2)$アルゴリズム (形式言語理論とオートマトン理論)
• FP^_>||>のある特徴付けと完全問題
• 実際的計算可能性の拡張について
• 確率的多項式時間アルゴリズムの能力について(計算アルゴリズムと計算量の基礎理論)

スポンサーリンク