ストリップス$_ {1}^{1}$の計算的複雑性の intermediate結果

This paper is based on Bylanderの結果に基づいて、Propositional STRIPS計画の計算的複雑性についてです。彼は，みずから地雷のみが使用可能な事態において，計画存在の決定はPSPACE完全であるかぎり，どのオペレータの前提条件と結果に限り二つを制限しても、プレースメントへの制約も2つの要素を制限してもNPハード性であることを示しました。 NP完全さは決まっていますが，Propositional STRIPSが一つの前後の解のオペレータのみを持っている場合，これは完全にNPです。 それに対する小さな解決策の仮説についての視線を照らし、小規模インスタンスに対してSATソルバーを呼び出し、実_literalグラフを開発し並びますをペトリネットにマッピングします。

arXiv:2602.08708v1 Announce Type: new 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.