文献

J-GLOBAL ID：201702222696251336   整理番号：17A1503278

計数と比較に基づく複雑さクラスΘK Pの新しい特性化【Powered by NICT】

A novel characterization of the complexity class Θ k P based on counting and comparison

著者 (2件)： Lukasiewicz Thomas (Department of Computer Science, University of Oxford, United Kingdom) ,  Malizia Enrico (Department of Computer Science, University of Oxford, United Kingdom)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 694  ページ： 21-33  発行年： 2017年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： 計算量クラスΘ2P,NPオラクルに多くの呼を対数的最もで多項式時間における決定論的チューリング機械によって認識可能言語のクラスは,文献における広範な注目を集めている。その完全問題は,異なる特定タスクによってキャラクタライズされるが,NP問題の最適解はユニークであるか,あるいはかどうか,ある意味では「奇数」(例えば,そのサイズは奇数であるかどうか)を決定する。本論文では,このクラスの新しい特徴づけと多項式階層のk番目レベルへの一般化ΘkPを導入した。ΘkPの問題は,その解が「イエス」におけるインスタンスの数はB.よりも大きいかどうか,二ΣK, 1P-完全な(またはΠK, 1P-完全)問題のインスタンスのAおよびB二与えられた集合のための,決定含むものもあることを示した。さらに,この新しい特性化に基づいて,ΘkP-硬さのための新しい十分条件を提供する。一般問題Comp有効_,Θk+1P完全わかるを定義した。Comp有効_はAの有効な式の数である。特により大きいかどうか,高々k交互量化記号を用いて定量化Boole公式の二セットAおよびB,決定の問題である,Comp有効1の特殊な場合である,セットは他のセットよりも充足可能Boole式を含むかどうか決めるという問題Comp Satは非常に直感的Θ2P完全問題としてそれ自身を実証した。それにもかかわらず,著者らの知識では,これまでにその形式的定義がされていない。事実,ここで導入した数と比較意味論への厳密な遵守,Comp有効_は「イエス」の数-二集合内の事例の計数と比較を含む問題のΘkP-硬さを証明するために最も適切なツールの一つである。mCPネット上のMax投票方式のΘ2P-硬さはこの論文で導入したΘkPの新しい特徴付けを介して容易に得られることを示すことにより,これを支持する。Copyright 2017 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【Powered by NICT】

シソーラス用語： *キャラクタリゼーション ,  硬度 ,  投票 ,  十分条件 ,  Turing機械 ,  奇数 ,  量化記号 ,  多項式 ,  意味論 ,  言語
準シソーラス用語： 最適解 ,  多項式時間 ,  オラクル ,  計算量クラス ,  *計数 , 【Automatic Indexing@JST】

著者キーワード (5件)： 多項式階層 ,  オラクルを持つ計算 ,  計数と比較 ,  ΘK P ,  ΘK P完全問題

分類 (1件)： 計算理論  (JB02000A)

タイトルに関連する用語 (4件)： 計数 ,  複雑さ ,  クラス ,  特性化