文献

J-GLOBAL ID：202002217972501515   整理番号：20A0383700

有限領域における不完全性についてのオラクル分離予測【JST・京大機械翻訳】

An oracle separating conjectures about incompleteness in the finite domain

著者 (1件)： Dose Titus (Julius-Maximilians-Universitaet Wuerzburg, Germany)
資料名： Theoretical Computer Science  (Theoretical Computer Science)
巻： 809  ページ： 466-481  発行年： 2020年 
JST資料番号： T0022A  ISSN： 0304-3975  CODEN： TCSDIQ  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： オランダ (NLD)  言語： 英語 (EN)

抄録/ポイント： Pudlakは,対応する関連する予測の対を分離するオラクルに対する複雑さとasを証明するのに関連するいくつかの主要な複雑さ理論的予測をリストする。これらの予測の中で,すべての分離NP対のクラスは,多い完全な問題を持たない。NPは,P-最適証明システムを持つ多-1完全集合を含まず,NP∩oNPは,多くの完全な問題を持たない。この問題に対する一つの答えとして,著者らは,(他の)DisjNP,¬SAT,UP,およびNP ∩oNPの保持に関するオラクルを構築した。したがって,含意DisjNP ∧UP ∧ NP ∩oNP ⇒SATに対する関連性の証明はない。特に,Pudlakによる予測に関して,これはKhanikiによる結果を拡張した。Copyright 2020 Elsevier B.V., Amsterdam. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 不整 ,  *含意
準シソーラス用語： 複雑性 ,  オラクル , 【Automatic Indexing@JST】

著者キーワード (5件)： 互いに素なNP対 ,  証明システム ,  P-最適 ,  アップ ,  オラクル

分類 (2件)： 図形・画像処理一般  (JE04010I) ,  グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (3件)： 不完全性 ,  オラクル ,  予測