Temporal Epistemic Gossip Problems
Temporal Epistemic Gossip Problems
复制标题
时间认知八卦问题
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Julien Vianey
中科院分区：
文献类型：
--
作者：
Martin C. Cooper;A. Herzig;Frédéric Maris;Julien Vianey
流言问题是规划问题，其中几个代理人必须通过两个代理人之间的电话共享信息（“秘密”）。在认识论流言问题中，目标可以是获得更高阶的知识，即，关于其他代理知识的知识;最后，在呼叫中，代理不仅传达秘密，而且传达代理的秘密知识、代理关于其他代理的秘密知识的知识等。这些约束有两种：要么规定两个代理之间的呼叫必须在某个时间点进行，要么规定呼叫可以在某个可能的（一组）时间间隔内进行。在非时态版本中，两个代理之间的调用要么总是可能的，要么总是不可能的。我们调查的复杂性计划存在问题在这个一般的设置。关于上界，我们证明了在一般情况下，它是在NP中，当问题是非时态的，目标是一个积极的认知公式时，它是在P中。至于下界，我们证明NP-完全性的两个片段：可能是负面的目标，即使在非时间的情况下，和时间的限制，即使目标是一组积极的原子的问题。
Gossip problems are planning problems where several agents have to share information (‘secrets’) by means of phone calls between two agents. In epistemic gossip problems the goal can be to achieve higher-order knowledge, i.e., knowledge about other agents’ knowledge; to that end, in a call agents communicate not only secrets, but also agents’ knowledge of secrets, agents’ knowledge about other agents’ knowledge about secrets, etc. Temporal epistemic gossip problems moreover impose constraints on the times of calls. These constraints are of two kinds: either they stipulate that a call between two agents must necessarily be made at some time point, or they stipulate that a call can be made within some possible (set of) interval(s). In the non-temporal version, calls between two agents are either always possible or always impossible. We investigate the complexity of the plan existence problem in this general setting. Concerning the upper bound, we prove that it is in NP in the general case, and that it is in P when the problem is non-temporal and the goal is a positive epistemic formula. As for the lower bound, we prove NP-completeness for two fragments: problems with possibly negative goals even in the non-temporal case, and problems with temporal constraints even if the goal is a set of positive atoms.
八卦协议公平终止的可判定性
DOI：
10.29007/62s4
发表时间：
--
期刊：
--
影响因子：
--
作者：
Apt K
通讯作者：
Apt K
影响因子：
--
作者：
Apt K
通讯作者：
Apt K