抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
3SUM仮説,APSP仮説およびSETHは,細粒複雑性における3つの主な仮説である。これまで,この領域内で,最初の2つの仮説は主に計算のWord RAMモデルにおける整数入力である。「Real APSP」と「Real 3SUM」仮説は,APSPと3SUM仮説が,実際のRAMモデルの妥当なバージョンで実数値入力に対して保持されていることを主張し,それらの整数対応物よりもさらに信頼できる。Integer 3SUM仮説の少なくとも1つ,Integer APSP仮説またはSETHは真の,Abboud,Vassievska W.およびYu[STOC 2015]は,Triangle Collectionと呼ばれる問題はn-ノードグラフ上でn ̄3-o(1)時間を必要とすることを示したものであるという非常に信頼できる仮説の下では,この仮説の下では,真の,Abboud,Vassievska W.およびYu [STOC 2015]は,n-ノードグラフ上でn ̄3-o(1)時間を必要とすることを示した。著者等の主な結果は,実際の3SUMの少なくとも1つ,実際のAPSP,およびOV仮説が真実である,より信頼できる仮説の下で,All-Color-Pairs Triangle Collectionと呼ばれるTriangle Collectionの僅かな一般化のための非自明な下限である。事前低減の僅かな修正と組み合わせて,著者らは,(静的)ST-Maxフロー問題および動的Maxフローのような問題に対する多項式条件付き下限を,現在,新しい弱い仮説の下で得た。著者らの主な結果は,次の2つの低減ラインに構築される。All-Edge Sparse Triangle問題に対する実際のAPSPと実際の3SUM硬度。事前削減は,これらの問題の整数変異体からのみ働いた。Boole行列乗算問題のバリアントに対する*実APSPとOV硬度。その方法に沿って,Triangle Collectionは問題のより単純な制限バージョンと等価であり,先行研究を単純化することを示した。また,本技法は,実際の3SUM仮説に基づくInteger All-Number 3SUMの超線形下限,およびOV仮説に基づくストリングマッチング問題に対する厳密な下限のような,他の興味深い意味を持つ。【JST・京大機械翻訳】
