論文の概要: Extended Version of: On the Structural Hardness of Answer Set
Programming: Can Structure Efficiently Confine the Power of Disjunctions?
- arxiv url: http://arxiv.org/abs/2402.03539v1
- Date: Mon, 5 Feb 2024 21:51:36 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 17:50:54.332690
- Title: Extended Version of: On the Structural Hardness of Answer Set
Programming: Can Structure Efficiently Confine the Power of Disjunctions?
- Title（参考訳）: 拡張バージョン: 解集合プログラミングの構造的硬さについて: 構造は分断の力を効率的に定義できるか?
- Authors: Markus Hecher, Rafael Kiesel
- Abstract要約: プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。
我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。
本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
- 参考スコア（独自算出の注目度）: 21.10339925217772
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Answer Set Programming (ASP) is a generic problem modeling and solving
framework with a strong focus on knowledge representation and a rapid growth of
industrial applications. So far, the study of complexity resulted in
characterizing hardness and determining their sources, fine-grained insights in
the form of dichotomy-style results, as well as detailed parameterized
complexity landscapes. Unfortunately, for the well-known parameter treewidth
disjunctive programs require double-exponential runtime under reasonable
complexity assumptions. This quickly becomes out of reach. We deal with the
classification of structural parameters for disjunctive ASP on the program's
rule structure (incidence graph).
First, we provide a polynomial kernel to obtain single-exponential runtime in
terms of vertex cover size, despite subset-minimization being not represented
in the program's structure. Then we turn our attention to strictly better
structural parameters between vertex cover size and treewidth. Here, we provide
double-exponential lower bounds for the most prominent parameters in that
range: treedepth, feedback vertex size, and cliquewidth. Based on this, we
argue that unfortunately our options beyond vertex cover size are limited. Our
results provide an in-depth hardness study, relying on a novel reduction from
normal to disjunctive programs, trading the increase of complexity for an
exponential parameter compression.
- Abstract（参考訳）: Answer Set Programming(ASP)は、知識表現と産業アプリケーションの急速な成長に焦点を当てた、汎用的な問題解決フレームワークである。
これまでの複雑性の研究は、ハードネスの特徴付けとソースの決定、二分法的な結果の形での詳細な洞察、そして詳細なパラメータ化された複雑さのランドスケープに繋がった。
残念なことに、よく知られたパラメータツリー幅分離プログラムは、合理的な複雑性の仮定の下で二重指数実行を必要とする。
これはすぐに手が届かない。
我々は,プログラムの規則構造(インシデンスグラフ)上の分離型aspのための構造パラメータの分類を扱う。
まず,プログラム構造に表現されないサブセット最小化にもかかわらず,頂点被覆サイズの観点から単一指数ランタイムを得る多項式カーネルを提案する。
次に、頂点被覆サイズと木幅の間の厳密な構造パラメータに注意を向ける。
ここでは、木深さ、フィードバック頂点サイズ、斜め幅という、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。
これに基づいて、残念ながら、頂点被覆サイズを超える選択肢は限られていると論じる。
本研究は, パラメータ圧縮の複雑さの増大を, 正規化プログラムから解離プログラムへの新たな還元に頼って, 奥行きの硬さについて検討した。
関連論文リスト
- Solving Projected Model Counting by Utilizing Treewidth and its Limits [23.81311815698799]
予測モデルカウント(PMC)を解く新しいアルゴリズムを提案する。
いわゆる「ツリー幅」が最も顕著な構造パラメータの1つであるという観測から着想を得て,本アルゴリズムは入力インスタンスの一次グラフの小さなツリー幅を利用する。
論文 参考訳（メタデータ） (2023-05-30T17:02:07Z) - SE-GSL: A General and Effective Graph Structure Learning Framework
through Structural Entropy Optimization [67.28453445927825]
グラフニューラルネットワーク(GNN)は、構造的データ学習のデファクトソリューションである。
既存のグラフ構造学習(GSL)フレームワークには、堅牢性と解釈性がない。
本稿では、構造エントロピーと符号化木に抽象化されたグラフ階層を通して、一般的なGSLフレームワークSE-GSLを提案する。
論文 参考訳（メタデータ） (2023-03-17T05:20:24Z) - DepGraph: Towards Any Structural Pruning [68.40343338847664]
我々は、CNN、RNN、GNN、Transformersのような任意のアーキテクチャの一般的な構造解析について研究する。
本稿では,階層間の依存関係を明示的にモデル化し,包括的にグループ化してプルーニングを行う汎用かつ完全自動な手法であるemphDependency Graph(DepGraph)を提案する。
本研究では,画像用ResNe(X)t,DenseNet,MobileNet,Vision Transformer,グラフ用GAT,3Dポイントクラウド用DGCNN,言語用LSTMなど,さまざまなアーキテクチャやタスクに関する手法を広範囲に評価し,言語用LSTMと並行して示す。
論文 参考訳（メタデータ） (2023-01-30T14:02:33Z) - Characterizing Structural Hardness of Logic Programs: What makes Cycles
and Reachability Hard for Treewidth? [9.480212602202517]
本稿では、よく知られたエンコーディングを超えるSATから通常のASPへの新規な削減について述べる。
これは依存性グラフのサイクル長の必要な機能的依存性を確立することによって、きめ細かい方法で硬さを特徴づける。
論文 参考訳（メタデータ） (2023-01-18T12:29:45Z) - Threshold Treewidth and Hypertree Width [37.90910578253212]
樹木幅と高木幅は、制約満足度(CSP)の文脈における構造パラメータとして非常に成功したことが証明されている。
ここでは、新しいしきい値の概念を通じて、木とハイパーツリーの幅を拡大する。
我々は、閾値木幅とハイパーツリー幅を計算するための効率的な理論的アルゴリズムと経験的アルゴリズムを得る。
論文 参考訳（メタデータ） (2022-10-13T13:53:59Z) - Treewidth-aware Reductions of Normal ASP to SAT -- Is Normal ASP Harder
than SAT after All? [9.480212602202517]
木幅を考えると、通常のASPのフラグメントはSATよりもわずかに難しいことが判明した。
本報告では, 通常のASPからSATへの新規な縮小について実証的研究を行い, 既知分解による木幅上界の比較を行った。
論文 参考訳（メタデータ） (2022-10-07T13:40:07Z) - MLPruning: A Multilevel Structured Pruning Framework for
Transformer-based Models [78.45898846056303]
プルーニングは、大きな自然言語処理モデルに関連するメモリフットプリントと計算コストを削減する効果的な方法である。
我々は,頭部刈り込み,行刈り,ブロックワイズ刈りという3つの異なるレベルの構造化刈り込みを利用する,新しいマルチレベル構造化刈り込みフレームワークを開発した。
論文 参考訳（メタデータ） (2021-05-30T22:00:44Z) - Lower Bounds and Accelerated Algorithms for Bilevel Optimization [62.192297758346484]
バイレベル最適化は、最近の機械学習問題に広く応用されているため、近年、関心が高まりつつある。
結果がminimaxアプリケーションよりも難しいことを示します。
論文 参考訳（メタデータ） (2021-02-07T21:46:29Z) - Convex Polytope Trees [57.56078843831244]
コンベックスポリトープ木(CPT)は、決定境界の解釈可能な一般化によって決定木の系統を拡張するために提案される。
木構造が与えられたとき,木パラメータに対するCPTおよび拡張性のあるエンドツーエンドトレーニングアルゴリズムを効率的に構築する。
論文 参考訳（メタデータ） (2020-10-21T19:38:57Z) - Refined bounds for algorithm configuration: The knife-edge of dual class
approximability [94.83809668933021]
トレーニングセットが、トレーニングセット上でのパラメータの平均メトリックのパフォーマンスが、予想される将来的なパフォーマンスに最も近いことを保証するために、どの程度の規模が必要かを調査する。
この近似が L-無限ノルムの下で成り立つなら、強いサンプル複雑性境界を与えることができる。
我々は、コンピュータ科学において最も強力なツールの一つである整数プログラミングの文脈において、我々の限界を実証的に評価する。
論文 参考訳（メタデータ） (2020-06-21T15:32:21Z) - Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である
本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。
また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文 参考訳（メタデータ） (2020-01-13T13:16:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。