論文の概要: Characterizing Structural Hardness of Logic Programs: What makes Cycles
and Reachability Hard for Treewidth?
- arxiv url: http://arxiv.org/abs/2301.07472v1
- Date: Wed, 18 Jan 2023 12:29:45 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-19 16:09:28.623058
- Title: Characterizing Structural Hardness of Logic Programs: What makes Cycles
and Reachability Hard for Treewidth?
- Title（参考訳）: 論理プログラムの構造的硬さを特徴づける: 周期と到達性が木幅に困難になる理由
- Authors: Markus Hecher
- Abstract要約: 本稿では、よく知られたエンコーディングを超えるSATから通常のASPへの新規な削減について述べる。
これは依存性グラフのサイクル長の必要な機能的依存性を確立することによって、きめ細かい方法で硬さを特徴づける。
- 参考スコア（独自算出の注目度）: 9.480212602202517
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Answer Set Programming (ASP) is a problem modeling and solving framework for
several problems in KR with growing industrial applications. Also for studies
of computational complexity and deeper insights into the hardness and its
sources, ASP has been attracting researchers for many years. These studies
resulted in fruitful characterizations in terms of complexity classes,
fine-grained insights in form of dichotomy-style results, as well as detailed
parameterized complexity landscapes. Recently, this lead to a novel result
establishing that for the measure treewidth, which captures structural density
of a program, the evaluation of the well-known class of normal programs is
expected to be slightly harder than deciding satisfiability (SAT). However, it
is unclear how to utilize this structural power of ASP. This paper deals with a
novel reduction from SAT to normal ASP that goes beyond well-known encodings:
We explicitly utilize the structural power of ASP, whereby we sublinearly
decrease the treewidth, which probably cannot be significantly improved. Then,
compared to existing results, this characterizes hardness in a fine-grained way
by establishing the required functional dependency of the dependency graph's
cycle length (SCC size) on the treewidth.
- Abstract（参考訳）: ASP(Answer Set Programming)は、KRにおけるいくつかの問題に対する問題モデリングおよび解決のフレームワークである。
また、計算複雑性の研究やハードネスとそのソースに関する深い洞察のために、ASPは長年研究者を惹きつけてきた。
これらの研究は、複雑性クラスにおける実りある特徴付け、二分法的な結果の詳細な洞察、および詳細なパラメータ化された複雑性ランドスケープをもたらす。
近年,プログラムの構造密度を計測する測度木幅に対して,正規プログラムのよく知られたクラスの評価は,満足度(SAT)を決定するよりもやや難しいことが期待されている。
しかし、ASP.NETのこの構造的パワーをどのように活用するかは不明だ。
本稿では,aspの構造的パワーを明示的に活用し,木幅をサブリニアに減少させることにより,おそらく大きくは改善されないであろう,satから通常のaspへの新たな還元について述べる。
そして、既存の結果と比較して、依存グラフのサイクル長(sccサイズ)の必要な機能依存性を確立することにより、きめ細かい方法で硬さを特徴付ける。
関連論文リスト
- AUCSeg: AUC-oriented Pixel-level Long-tail Semantic Segmentation [88.50256898176269]
画素レベルのAUC損失関数を開発し,アルゴリズムの一般化能力に関する依存性グラフに基づく理論的解析を行う。
また、重要なメモリ需要を管理するために、Tail-Classes Memory Bankを設計する。
論文 参考訳（メタデータ） (2024-09-30T15:31:02Z) - Enhancing Systematic Decompositional Natural Language Inference Using Informal Logic [51.967603572656266]
我々は,分解包含を注釈付けするための一貫した理論的なアプローチを導入する。
我々の新しいデータセットRDTEは、前回の分解エンターメントデータセットよりもかなり高い内部整合性(+9%)を持つことがわかった。
また,RDTE による知識蒸留によるエンテーメント分類器の訓練や,エンテーメントツリー推論エンジンへの導入により,精度と検証精度が向上することが確認された。
論文 参考訳（メタデータ） (2024-02-22T18:55:17Z) - Extended Version of: On the Structural Hardness of Answer Set
Programming: Can Structure Efficiently Confine the Power of Disjunctions? [21.10339925217772]
プログラムのルール構造上での解離的ASPの構造パラメータの分類に対処する。
我々は、その範囲で最も顕著なパラメータに対して、二重指数下界を提供する。
本研究は, 通常のプログラムから解離プログラムへの新規な縮小に頼って, 深部硬度調査を行う。
論文 参考訳（メタデータ） (2024-02-05T21:51:36Z) - When Do Program-of-Thoughts Work for Reasoning? [51.2699797837818]
本稿では,コードと推論能力の相関性を測定するために,複雑性に富んだ推論スコア(CIRS)を提案する。
具体的には、抽象構文木を用いて構造情報をエンコードし、論理的複雑性を計算する。
コードはhttps://github.com/zjunlp/EasyInstructのEasyInstructフレームワークに統合される。
論文 参考訳（メタデータ） (2023-08-29T17:22:39Z) - 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) - 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) - Provable Reinforcement Learning with a Short-Term Memory [68.00677878812908]
我々はPMDPsの新しいサブクラスについて研究し、その潜在状態は、最近の短い長さ$m$の履歴によって復号化することができる。
特に、リッチ・オブザーブレーション・セッティングにおいて、指数関数的にスケールするサンプル複雑性を持つ新しい「モーメントマッチング」アプローチを用いて、新しいアルゴリズムを開発する。
以上の結果から,これらの環境下での強化学習には短期記憶が十分であることが示唆された。
論文 参考訳（メタデータ） (2022-02-08T16:39:57Z) - Learning Bayesian Networks in the Presence of Structural Side
Information [22.734574764075226]
本研究では,システムに関する構造的側面情報が得られる場合に,変数の集合のベイズネットワーク(BN)を学習する問題について検討する。
そこで我々は,そのような知識を学習プロセスに効率的に組み込むアルゴリズムを開発した。
我々の研究の結果、木幅の有界BNは複雑に学習できることが示されている。
論文 参考訳（メタデータ） (2021-12-20T22:14:19Z) - Efficient Micro-Structured Weight Unification and Pruning for Neural
Network Compression [56.83861738731913]
ディープニューラルネットワーク(DNN)モデルは、特にリソース制限されたデバイスにおいて、実用的なアプリケーションに不可欠である。
既往の非構造的あるいは構造化された重量刈り法は、推論を真に加速することはほとんど不可能である。
ハードウェア互換のマイクロ構造レベルでの一般化された重み統一フレームワークを提案し,高い圧縮と加速度を実現する。
論文 参考訳（メタデータ） (2021-06-15T17:22:59Z) - Efficient and Scalable Structure Learning for Bayesian Networks:
Algorithms and Applications [33.8980356362084]
事業要件を総合的に満たす新しい構造学習アルゴリズム「LEAST」を提案します。
LEASTはデプロイされ、毎日数千の実行で20以上のアプリケーションに対応します。
大規模遺伝子発現データ解析や説明可能なレコメンデーションシステムなど,新しい領域におけるbn構造学習の適用可能性の最小化が期待できることを示す。
論文 参考訳（メタデータ） (2020-12-07T09:11:08Z) - Structural Decompositions of Epistemic Logic Programs [29.23726484912091]
認識論理プログラム(ELP)は標準解集合プログラミング(ASP)の一般的な一般化である
本研究では, 木幅境界で構造特性を示すELPに対して, 線形時間で中心的な問題を解くことができることを示す。
また、これらの境界に従属する完全な動的プログラミングアルゴリズムも提供します。
論文 参考訳（メタデータ） (2020-01-13T13:16:13Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。