中間的な複雑さをもつ問題のクラスについて
スポンサーリンク
概要
- 論文の詳細を見る
計算量理論の中心的課題は与えられた問題をその複雑さによって分類する事である。この目的を達成するため様々な問題のクラスが導入されそのクラスに関して完全となる問題が数多く示されている。一方、導入されたクラスが大まかであるため分類されずに残っている問題も多い。例えば、グラフ同型問題や無向グラフの到達可能性判定問題(UGAP)などである。この状況をUGAPについて述べると次のようになる。UGAPはNL(非決定性対数領域)に属するがNL完全であるかDL(決定性対数領域)に属するかは判っていない。一般には、そのどちらでもない、いわば、中間的複雑さをもつと予想されている。そこで本稿では、このような中間的複雑さをもつ問題を分類するためのクラスを特にDLとNLの間に導入しそのクラスが中間的であるという根拠を与える。更に、そのクラスに関して完全となる具体的な問題を示す。
- 一般社団法人情報処理学会の論文
- 1986-10-01
著者
関連論文
- 国際コラボレーションによる日本文学研究資料情報の組織化と発信--科学研究費基盤研究(S)による (特集 台湾からみる日本--進化する国際コラボレーション) -- (台湾からみる日本の古典)
- メタデータによるマルチメディアデータ統合の試み
- 単語の意味の学習について
- 情報検索システムのための,単語の意味の空間的表現と学習
- 中間的な複雑さをもつ問題のクラスについて
- 日本文学研究情報組織化のための国際コラボレーション計画
- 国文学研究支援のためのSGML/XMSデータシステム : 国文学データ共有のための標準化(人文科学における情報知識処理)
- 文学研究のためのデータベースシステムの諸問題--文学データ共有のための標準化 (特集 コンピュータによる日本語研究の新展開)
- 国文学と電子資料館
- 国文学と電子資料館
- P.マコーダック著, 黒川利明訳, コンピュータは考える : 人工知能の歴史と展望, 東京, 培風館, 1983, 431p., 2,500円
- データベースは研究に影響を与えるか : 国文学研究資料館「日本古典文学本文データベース」利用者調査
- マイクロ資料目録CD-ROMと検索システムの開発 : パーソナル環境での国文学研究支援
- 国文学電子資料館システム--マルチメディアデータベースへのSGMLの適用
- 国文学情報システム (特集 学術情報システム)
- 文化科学研究分野における情報資源共有化について(第13回(2005年度)研究報告会講演論文集)
- 87-14 成長的文脈依存言語は多項式時間認識可能である
- 線型領域におけるオルタネーションの能力について(計算アルゴリズムの基礎理論)
- 85-26 DurisとGalilの技法の変形
- 池田秀人 著, "アメリカ合衆国における図書館自動化システム", 紀伊國屋, A5判, 217p., \3,000, 1984
- Positive relativizations of low level complexity classes(Mathematical Foundations of Computer Science and Their Applications)
- 情報と知識(情報知識学会創立20周年記念特別号)
- 「知識の源泉は,..」
- 日本文学国際共同研究プロジェクトの中間研究報告
- お知らせ 〔情報知識学会〕第1回論文賞について
- 特集「人文科学における情報知識処理」(「人文科学における情報知識処理」)
- 情報国文学について考える
- 日本文学研究とコンピュータ (特集 転換期の古典)
- 日本古典文学作品本文データベース(実験版)の試験公開 (特集 古典学研究--現代における古典学の役割)
- 国文学作品のテキストデータ記述ルールについて
- 国文学研究とコンピュータ : 電子本「漱石と倫敦」考を作る
- 奈良絵本デ-タベ-スの開発研究
- 国文学における文献資料の画像データベースとその流通
- 国文学における情報の考察とデータベースの構築
- 日本古典文学の本文データベース
- 国文学におけるマルチメディアデータベース (メディアの統合とメディア変換)
- 大学LAN