抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
計算量クラスΘ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】