論文の概要: Intermediate Results on the Complexity of STRIPS$_{1}^{1}$
- arxiv url: http://arxiv.org/abs/2602.08708v1
- Date: Mon, 09 Feb 2026 14:21:10 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-02-10 20:26:25.284353
- Title: Intermediate Results on the Complexity of STRIPS$_{1}^{1}$
- Title（参考訳）: STRIPS$_{1}^{1}$の複雑さに関する中間結果
- Authors: Stefan Edelkamp, Jiří Fink, Petr Gregor, Anders Jonsson, Bernhard Nebel,
- Abstract要約: 1つの前提条件と1つの効果しか持たない作用素を持つ命題STRIPSがNP完全であるかどうかは不明である。
我々はSATソルバを小さなインスタンスに呼び出し、リテラルグラフを導入し、それをペトリネットにマッピングする。
- 参考スコア（独自算出の注目度）: 4.706932040794695
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper is based on Bylander's results on the computational complexity of propositional STRIPS planning. He showed that when only ground literals are permitted, determining plan existence is PSPACE-complete even if operators are limited to two preconditions and two postconditions. While NP-hardness is settled, it is unknown whether propositional STRIPS with operators that only have one precondition and one effect is NP-complete. We shed light on the question whether this small solution hypothesis for STRIPS$^1_1$ is true, calling a SAT solver for small instances, introducing the literal graph, and mapping it to Petri nets.
- Abstract（参考訳）: 本稿では、命題STRIPS計画の計算複雑性に関するBylanderの結果に基づく。
彼は、基底リテラルのみが許されるとき、作用素が2つの前提条件と2つの後条件に制限されている場合でも、計画の存在を決定することはPSPACE完全であることを示した。
NPハードネスは解決されるが、1つのプレ条件と1つの効果しか持たない作用素を持つ命題STRIPSがNP完全であるかどうかは不明である。
STRIPS$^1_1$に対するこの小さな解の仮説が真かどうかという問題に光を当て、小さなインスタンスに対してSATソルバを呼び出し、リテラルグラフを導入し、それをペトリネットにマッピングする。
関連論文リスト
- Learning Deterministic Finite-State Machines from the Prefixes of a Single String is NP-Complete [0.0]
入力サンプルがプレフィックスクローズされた場合の計算複雑性について検討した。
サンプル集合がバイナリ文字列のすべてのプレフィックスで構成されている場合,問題はNPハードで近似可能であることを示す。
論文 参考訳（メタデータ） (2026-01-18T23:28:36Z) - Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
ROC曲線の下の領域(AUC)は、クラス不均衡と決定制約の両方を持つ実世界のシナリオにおける重要な評価指標である。
PAUC最適化の近似ギャップを埋めるために,2つの簡単なインスタンス単位のミニマックス修正を提案する。
得られたアルゴリズムは、サンプルサイズと典型的な一方方向と双方向のPAUCに対して$O(-2/3)$の収束率の線形パーイテレーション計算複雑性を享受する。
論文 参考訳（メタデータ） (2025-12-01T02:52:33Z) - Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。
1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
論文 参考訳（メタデータ） (2024-11-29T05:29:47Z) - Homomorphisms and Embeddings of STRIPS Planning Models [4.594173051888471]
1つ目はGI完全であり、理論上は準多項式時間で解けることを示す。
残りの問題はNP完全であることが証明されているが、可能であれば同型を構築するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-24T11:43:18Z) - Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
単次元モデル(Single-Index Models)は、植木構造における高次元回帰問題である。
我々は,統計的クエリ (SQ) と低遅延多項式 (LDP) フレームワークの両方において,計算効率のよいアルゴリズムが必ずしも$Omega(dkstar/2)$サンプルを必要とすることを示した。
論文 参考訳（メタデータ） (2024-03-08T18:50:19Z) - Simple Binary Hypothesis Testing under Local Differential Privacy and
Communication Constraints [8.261182037130407]
局所差分プライバシー (LDP) と通信制約の両面から, 単純な二分仮説テストについて検討する。
我々はその結果をミニマックス最適かインスタンス最適かのどちらかとみなす。
論文 参考訳（メタデータ） (2023-01-09T18:36:49Z) - Semantic Probabilistic Layers for Neuro-Symbolic Learning [83.25785999205932]
我々は構造化出力予測(SOP)のための予測層を設計する。
予測が事前に定義されたシンボリック制約のセットと一致していることを保証するため、任意のニューラルネットワークにプラグインすることができる。
我々のセマンティック確率層(SPL)は、構造化された出力空間上で複雑な相関や制約をモデル化することができる。
論文 参考訳（メタデータ） (2022-06-01T12:02:38Z) - Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。
線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
論文 参考訳（メタデータ） (2022-04-20T21:15:38Z) - Efficient Explanations With Relevant Sets [30.296628060841645]
本稿では,$delta$-relevant 集合の実用的限界に対処するための解について検討する。
$delta$-relevant 集合の部分集合の計算は NP であり、NP のオラクルへの多くの呼び出しで解ける。
論文 参考訳（メタデータ） (2021-06-01T14:57:58Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
我々の懸念は、標準的なデータベースクエリへの記述とそれらの最適な書き換えを介し、クエリに応答する際のデータ複雑さを効率的に決定することである。
我々は、疎結合シロップ(d-シロップ)と呼ばれるブール共役型クエリに焦点を当てる。
一部のd-シロップは指数的な大きさの分解能しか持たないが、そのうちのいくつかは二重指数サイズの正存在量書き換えと単帰的データログ書き換えのみである。
論文 参考訳（メタデータ） (2020-06-07T14:47:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。