概率抽象论证中基本问题的复杂性

（）人工智能268（2019）1概率抽象论证中基本问题的复杂性：超越独立性Bettina Fazzingaa，Sergio Flescab，Filippo Furfarob，aICAR - CNR -意大利bDIMES-卡拉布里亚大学-意大利Ar t i cl e i nf o a b st r a ct文章历史：2017年7月28日收到收到修订版，2018年8月8日接受，2018年在线发售2018年关键词：概率抽象论证复杂性经典的验证和接受问题的概率对应的复杂性研究概率抽象论证框架（prAAFs），在一个更一般的设置比在当前的文献中，其中的复杂性已被描述为只有在参数/失败之间的独立性的假设下。问题的复杂性范围从FP到FP#P-完成，带FP ||NP完全的 情况下，取决于扩展 的语义，用于对prAAF进行编码的表征范式，以及参数/失败之间的强加相关性，从而提供了对几个方面的敏感性的透彻分析。 在这方面， 为了 以允许 为了研究论证/失败之间的不同形式的相关性对复杂性的影响，引入了一种新的prAAF形式，称为gen。它是基于世界集描述符和世界集集代表概率的著名范例，它允许的相关性，可以很容易地和明确地表达。有趣的是，gen的引入也被证明是一个独立的贡献，作为一个强大的代表范式prAAF，由于其高表达性，紧凑性，并支持用户友好的机制来定义相关性的可能性。2018 Elsevier B.V.保留所有权利。1. 介绍1.1. 抽象论证框架（AAF）在过去的十年中，已经提出了几个论证框架，目的是适当地模拟两个或两个以上当事人之间的争议。通常，论证框架既模拟了当事人提出支持其论点的论证的可能性，也模拟了一些论证反驳其他论证的可能性。 虽然论证 由于它与哲学和法律密切相关，因此人们对人工智能产生了极大的兴趣，将其作为一种推理模型，用于表示对话、做出决策以及处理不一致性和不确定性[1一个强大而简单的论证框架是在开创性的论文[4]中提出的，称为抽象论证框架（AAF）。一个AAF是一个争论的论证图方面的表示 A，D，其中A是节点的集合（每个节点称为参数），D是边 的集合（每个边称为失败， 或者等价地称为攻击）。*通讯作者。电子邮件地址：furfaro@dimes.unical.it（F.Furfaro）。https://doi.org/10.1016/j.artint.2018.11.0030004-3702/ 2018 Elsevier B. V.保留所有权利。目录可在ScienceDirect人工智能www.elsevier.com/locate/artint2B. Fazzinga等人 /《人工智能》268（2019）1-29基本上，一个参数是一个抽象的实体，可以攻击和/或被其他参数攻击，攻击表示一个论点反驳/削弱另一个论点。实施例1（受[ 5 ]中实施例1的启发）。玛丽和马克的辩护律师想对涉及他的当事人的抢劫案的审判结果进行推理。案件的论点如下，其中安是一个潜在的证人：答：b：c：“安说她确信就在抢劫案发生前，他在银行外面看到了玛丽，她还认为她可能也在那里看到了马克论点a和b支持被告无罪，c意味着一个潜在的证人对玛丽和马克的清白这种情况可以由AAFA建模，其参数集为{a，b，c}，其失败关系由以下组成：缺点是δac=（a，c），δca=（c，a），δbc=（b，c）和δcb=（c，b），这意味着论点a和b都被c攻击，它们都反击c。□AAF的几种语义，如可容许的，稳定的，优选的，完全的，接地的，理想集，理想和半稳定的， [4，6基本上，这些语义中的每一个都对应于一些属性，这些属性“证明”一组参数是否可以有利地用于支持讨论中的观点。例如，在容许语义下，如果S是“无约束的 在S中的参数之间没有失败）并且相对于其它参数是“鲁棒的”（即， 在S之外攻击S中的一个论点的每一个论点都被S中的一个论点反击）。这意味着谁使用参数S的集合，讨论不自相矛盾，可以反驳其他当事人可能提出的论点。的其他语义对应于确定一组论点是否是争议中的“好观点”的其他方式，并将在本文的核心部分进行描述1.2. 论证中的不确定性：概率AAF事实上，在现实世界中，争论和失败往往是不确定的。例如，考虑一个参数a（或失败δ）对参考文本中所报告的事实描述的解释或翻译进行编码。 然后，a（或δ）可能是不确定的，因为原始段落可能具有不同于由a编码的解释。（ 或δ）。在法律场景中，这种情况发生在对法律的不同解释进行编码的论点论点a的另一种形式的不确定性对应于这样一个事实，即不能保证论点a将在争议中实际提出（例如，证人可能不决定出庭）或被协调争议的裁判接受。 争议（例如，法官可以决定排除当事方提出的论点）。 类似地，在法律纠纷中，两个论点之间的失败可能是不确定的：例如，陪审团可以被指示考虑被反驳的论点另一种则取决于对法律先例的解释方式因此，已经提出了几种建议，通过考虑与论点和/或失败相关联的权重、偏好或概率来对AAF中的不确定性进行建模。基于概率论对不确定性进行建模的最流行的方法之一是所谓的星座方法[9-的各项工程在研究prAAF的文献中，关于如何指定场景中的概率分布函数（pdf）的假设可能不同。例如，在[9]中，pdf被定义为“广泛的”，通过列举所有可能的场景以及每个场景的概率值。这种形式的prAAF将被表示为ex（“广泛“的简写是 “最大限度地表达”：它对概率分配没有任何限制，因此允许表达论点/失败之间的任何类型的相关性。另一方面，在[14]中，假设了论点和失败是独立的限制，这被用来简化概率的指定方式：pdf没有显式指定，正如与争论和失败相关的边际概率所暗示的那样。这种形式的prAAF将表示为ind（“independent“的简写但是更加紧凑。1.3. 论证框架上的推理：从确定性到概率性情景在确定性设置中，支持AAF推理的两个经典问题是：–sem;B. Fazzinga等人 /《人工智能》268（2019）1-293pC– 它属于语义SEM下的至少一个扩展。1基本上，这些问题的相关性在于，解决Extsem（S）支持关于在争议中提出一组论点是否是合理策略的决定，而解决Accsem（a）则将此分析集中在单个论点上。在概率设置中，存在要考虑的多个场景，并且集合S（分别，一个论点a）可以是扩展（分别地，在某些情况下是可以接受的，但在其他情况下则不行。因此，上述问题Extsem（S）和Accsem（a）的自然概率对应物P-Extsem（S）和P-Accsem（a）分别在于评估S是扩展和a直观地，分别在参数集和单个参数上求解P-Extsem（S）和P-Accsem（a）的实例，可以支持探索在争议中可以采用的可能策略的搜索空间，目的是组成一组提供良好成功机会的参数在本文的核心，我们将提供P-Extsem（S）和P-Accsem（a）的彻底复杂性表征，如下面更好地解释的那样1.4. 贡献在文献中，对Extsem（S）和Accsem（a）的复杂性进行了广泛研究，结果总结见表1和表2。关于同样问题的对应物的复杂性，概率设置。据我们所知，文献中仅有的结果是[16]和[17]中的那些，涉及P-Extsem（S）和P-Accsem（a）在ind形式的prAAF上的复杂性，而在ex形式的prAAF上没有提供严格的表征。在这方面，我们的第一个贡献是P-Extsem（S）和P-Accsem（a）在形式上例如：我们表明，根据扩展的语义，P-Extsem（S）和P-Accsem（a）要么在FP中（即， 它们可以在多项式时间内求解）或FP||NP-完成或在FP中||2.2（其中FP||C是一类可由确定性多项式时间图灵机解决的问题，该图灵机扩展了对该类的 o r a c l e 的 并行 调 用 。从这一点出发，为了提供一个洞察所考虑的问题的复杂性的来源，我们调查的敏感性的复杂性的类型的相关性（参数和/或失败之间）编码的prAAF。事实上，要进行这一分析，ex和ind两种范式都是不够的。一方面，ind不允许表达相关性。另一方面，在前相关性可以被编码，但隐含地：例如，可以通过将0概率分配给仅存在两个参数的可能场景来强制两个参数必须共存，但是从概率推断相关性的反向过程很难实现。因此，我们引入了一个新的prAAF（称为gen），其中用于在可能的场景中定义pdf的结构允许显式指定参数和失败之间的相关性（例如互斥和同现）。该框架基于著名的世界集描述符（WSDS）和WS-集范式，它被证明是一个完整而简洁的形式主义在[18，19]中用于指定可能世界上的PDF，并在概率数据库的上下文中得到了有益的应用。有趣的是，我们利用这样一个事实，即不同的句法限制wsds对应于允许不同形式的相关性被表达，并提供了一个复杂性分析的P-Extsem（S）和P-Accsem（a）为每个句法类，从而显示其复杂性的敏感性存在的不同形式的相关性参数/失败。作为附带贡献，值得注意的是gen及其子类不仅用于允许P-Extsem（S）和P-Accsem（a）的彻底复杂性表征，而且它们也可以被视为自身有效性的prAAF：事实上，它们提供了一种用于指定论证系统中的概率方面的新机制，并且可以在实际场景中被证明是有用的，正如下面更好地解释的那样1.5. 贡献的相关性P-Extsem（S）和P-Accsem（a）的复杂性研究从几个角度来看是相关的。一方面，寻找类F P的新的完全问题||NP 而FP#P甚至在其他研究领域也很有用的论证。事实上，在目前的文献中，已知FP完备的问题集||NP 或FP#P非常小（特别是对于FP||NP），因此扩大这一组可以帮助精确表征其他问题，从这 些 问题中存在到P-Ext sem（S）和P-Acc sem（a）的“自然”还原。另一方面，描述复杂性有助于推理解决问题的最合适策略。 在P-Extsem（S）和P-Accsem（a）的情况下，知道它们的复杂性可以帮助在1）可接受性和扩展的概率的精确计算（如果问题是易处理的，这是合理的选择）和2）诉诸于估计它（如果问题是可处理的，这是合理的选择）之间进行选择。难处理）。事实上，论证文献提供了一个在设计算法之前进行复杂性分析的重要性的例子：当PrAAF在[14]中首次引入时，提出了一种估计扩展概率的策略，因为它的精确计算被认为在合理的时间内是不可行的。接下来，1 接受问题也可以在怀疑语义下陈述，其中答案是肯定的，当且仅当a属于所有的扩展。在第8节中，我们将详细说明我们的结果如何容易地扩展到包括怀疑语义。4B. Fazzinga等人 /《人工智能》268（2019）1-29⊆ ×（）⊆ ∀ ∈∈⊆∈∈ ∈⊆={∈}∈ ∈ ⊆∈[ 16 ]中的复杂性研究表明：1）对于可容许和稳定的语义，精确评估在线性时间内是可行的，因此诉诸估计策略是没有动机的;2）对于其他语义，问题是棘手的，支持使用近似评估（例如，基于蒙特卡洛策略，如[14，20]中所做的）。 在这方面，值得注意的是，我们的调查发现了新的易处理的病例（特别是P-Extsem（S））在ind-d上，即，在这种情况下，假设失败是独立的，而在论点之间可以指定一些相关性），从而扩大了[16]中所示的易处理性岛屿（在所有争议条件本文的第二个贡献，即，gen及其子类的引入从实用的角度来看也是相关的：它们的表达性、紧凑性和能力的良好组合允许容易地指定不同的相关性，使得这些范例适合于在实际论证场景中容易地建模不确定性。 特别是，我们将证明，对gen施加一些语法限制会导致一个片段，该片段易于嵌入为用户友好的可视化界面的核心，其中常见的相关性（如XOR和共存约束）可以指定。1.6. 文件计划本文的结构如下。 在第2节中，我们介绍了本文其余部分中使用的概念和符号。具体而言，我们回顾了非概率性AAF和前和后形式的prAAF的基本原理，并回顾了P-Extsem（S）和P-Accsem（a）的正式定义。在第3节中，我们专注于ex形式的prAAF，并研究了P-Extsem（S）和P-Accsem（a）的复杂性。然后，在第4节中，我们介绍了范式gen及其子类，前前semsem在第5节中，我们完成了P-Ext问题复杂性的描述(S) 和P-Acc(a) 通过提供这些形式的prAAF的复杂性的表征。 在第6节中，我们从实践的角度讨论了形式gen的相关性，作为支持用户友好的概率和涉及论点和失败的相关性的机制的核心。最后，在第7节中，我们讨论了相关的工作，在第8节中，我们绘制了我们的结论，并讨论未来工作的可能方向2. 预赛2.1. 抽象论证框架（AAF）抽象论证框架[4]（AAF）是一对A，D，其中A是一个有限集合，其元素称为论证，D一A是关于A的二元关系，其元素称为失败（或攻击）。一个参数是一个抽象实体，它的作用由它与其他参数的关系决定给定参数a，b我们说a击败b当且仅当存在（a，b）D. 类似地，一个集合S A击败了一个参数b一当且仅当存在一个S使得a击败b;论证a击败S当且仅当存在b S使得a击败b。 给定一个参数集S A，我们定义S+为被S击败的参数集，即S+ a As. t。S击败A。集合S如果没有a，b，则称参数A是无冲突的A击败了B。一个参数a被称为可接受w.r.t.一组参数SA当且仅当b A使得b击败a，存在c S使得c击败b。一个AAF可以很自然地被看作一个图，称为论证图，其节点是A中的论证，其边是D中的失败。因此，我们经常使用术语2.2. AAF的语义和基本问题：Extsem（S）和Accsem（a）已经提出了几种AAF的语义来识别我们认为以下是众所周知的语义：可接受（AD），稳定（ST），完全（CO），接地（GR），优选（PR）[4]，理想集（IDS），理想（IDE）[6]和半稳定（SST）[8]。一个集合SA被称为：• 一个容许扩张当且仅当S是无冲突的且它的所有自变量都是可接受的. S;• 一个稳定扩张当且仅当S是无冲突的且S击败了A\S中的每个自变量;• 一个完全扩张当且仅当S是可容许的，并且S包含所有可接受的参数。S;• 一个接地扩张当且仅当S是一个极小（w.r.t.）（3）完整的参数集• 半稳定扩张当且仅当S是完全扩张，其中S∈S+是极大的（w.r.t.（c）;• 优选扩张当且仅当S是极大（w.r.t.）（3）完整的参数集• 理想集扩张当且仅当S是可容许的且S包含在每一个优选变元集中;• 理想扩张当且仅当S是极大（w.r.t.） 理想集扩张。在下文中，我们将由上面列出的语义组成的集合{ad，st，co，gr，pr，ids，ide，sst}表示为SEM实施例2. 考虑示例1的AAF（A，D），其中参数集合A是{a，b，c}，并且失败集合D是{δac=（a，c），δca=（c，a），δbc=（b，c），δcb=（c，b）}。由于S={a，b}是无接触的，并且a和b都是可接受的，S，然后B. Fazzinga等人 /《人工智能》268（2019）1-295∈={}={}=（）∈{（）|⊆ ∧⊆×}F（）{}联系我们==== −=S是可以接受的。很容易看出，、S1c、S2a和S3b是可容许扩张，而集合S4a，c是不可容许的，因为它不是无接触的.S2和S3都不是完整的，因为它们不包含所有可接受的参数：a）可接受的w.r.t. S2（S3）。集合S1、S2和S3是完全扩张.此外，S和S1也是稳定、半稳定和优选扩展。 它是唯一的接地扩展，它也是理想集和理想扩展□给定AAFαA、D、一组S一个参数，和一个语义sem我们定义函数ext（α，sem，S）如果S是根据sem的扩展，则返回true，否则返回false。验证一个参数集S是否是一个给定AAF上的扩展的基本问题是根据语义semSEM将表示为Ext sem（S）。基本上，求解Extsem（S）的实例意味着检查集合是否论证的合理性是争论中的一种合理策略，其中“合理”的含义被编码在所选择的语义中。关注一个单一的论点，而不是一组论点，是接受问题Accsem（a）背后的基本原理， 这是验证参数a是否属于指定语义下的至少一个扩展的问题2.3. 可能的AAF（prAAF）：ex和ind在抽象论证中对不确定性进行建模的一种行之有效的方法是所谓的星座方法，该方法包括考虑替代的可能场景，并为每个场景分配概率。基本上，每个场景都是一个AAF（正式名称为因此，概率AAF（prAAF）是三元组A， D， P，其中A和D分别是参数和失败的集合，并且P是集合Ar，DrArA Dr上的概率分布函数（pdf（Ar Ar）D由可能的AAF组成，分别将A和D的子集作为参数和失败。在文献中，可以找到不同的prAAF提案。主要区别在于可能的AAF上的pdfP的编码方式，我们将P最流行的表示范式表示为ex和ind。特别地，ex是prAAF的一种形式（即在[9，10，12]中的框架的基础上），其中可能的AAF被“广泛”地指定，通过逐个指示具有非零概率的情景以及它们中的每一个的概率。 也就是说，一个公式的prAAF是一个元组 （ A ， D ， α→ ， P→ ） ， 其 中 A 和 D 是参数和定义的集合，而 α→ 是 等 式 α→=α1 ， .， α 是 可能的AAF 中 未 分配的。zeroproprobabilityyandP→=αP（α1），. ，P（αm）are实施例3 （形式ex的prAAF的实例）。 考虑 的 集 的参数Aa，b，c和 失败 Dδac，δca，δbc，δcb 在示例1中介绍，并假设律师认为只有以下4种情况是可能的- 表：S1：S2：S3：S4：在另一个方向上，a和b将不会被感知“足够强大，足以摧毁C每个场景Si由以下列表中的AAFαiα1=（{a，b}，α 2=（{a，b，c}，{δac，δca，δbc，δcb}），α 3 =（{a，b，c}，{δca，δcb}），α 4 =（{a，b，c}，{δca}）。基本上，prAAFex的形式允许律师逐个定义哪些场景是可能的，然后分配基于她/他对场景的可能性的感知，向AAF提供与每个场景相对应的概率。例如，律师设定的pdf可能是：P（α1）0。1和P（α2）P（α3）P（α4）（1） P（α1））/3 0。3，这意味着律师认为有10%的可能性，安不会设法作证（由于她的健康状况不佳），而且，在她测试的情况下，其他三种情况都是等概率的。这种不确定性是通过如下公式F=（A，D，α→，P→）的公式来建模的：其中：A={a，b，c}，D={δca，δcb，δa c，δbc}，α→=[α1，. ，α4]且P→=[0. 1，0。三，零。三，零。3]。 □我们现在关注prAAF的形式，表示为ind[11，14在这里，可能的AAF和它们的pdf被隐含地定义，因为它们是通过为论点和失败分配边际概率并假设它们之间 也就是说，ind类型的prAAF是元组（A，D，PA，PD），其中A ={a1，. a m}和D ={δ1，.， δn}他们的责任。该模型的prAAF（A，D，α→，P→）的大小为O（|一| 关于我们|D|）（|α→| + |P→|）。6B. Fazzinga等人 /《人工智能》268（2019）1-29联系我们{}F（）F∈我的天=--=联系我们=（{}{}）=（{}{}）=（{}{}）=（{}{}）=（{}{}）（）.是论点和失败的集合，P AP（a1），.，P（a m），P DP（δ1），.， P（δn）是争论和失败的边际概率。独立性假设所隐含的可能场景下的pdfP和边际概率PA，PD如下。对于每个可能的AAFαi=（Ai，Di），其中Ai<$A，Di<$（Ai×Ai）<$D，概率P（αi）为：P（αi）=.P（a）×。.1−P（a）×。P（δ）×..1−P（δ）π，（1）a∈ Aia∈A\Aiδ∈Diδ∈D（αi）\Di其中D（αi）是Ai中的自变量之间D中的所有失败的集合，即D（αi）=D（Ai×Ai）。1、A的大小为0，A的大小为0，A的大小为0，A的大小为0。|一|关于我们|D|关于我们|P A|关于我们|P D|）。实施例4 （ind形式的prAAF的实例）。 考虑 的 集 参数Aa，b，c和 失败 Dδac，δca，δbc，δcb在实施例1中介绍。 如果律师认为任何论点的出现并不影响其他论点的存在（失败也是如此），则可以假定争议条款之间的独立性。因此，律师可以专注于每一个单独的论点和失败的发生概率与其他人分开。 例如，律师可以设置P（c）0。9（意味着Ann有10%的可能性无法作证）和P（ a）P（ b）1（意味着Mary和Marc肯定会作证）。此外，她/他可以设定P（δca）1（这意味着她/他确信陪审团会认为安类似地，她/他可以设置P（δcb）0。P（δac）P（δbc）0. 4.鉴于此，由于参数被认为是独立的，因此由ind建模的可能场景是所有AAF A i，D i，其中A i是A的子集 和 Di 一个失败的子集， D 中的参数之间 Ai. 具体来说，有9种可能的AAF，其中9个中有4个等于α1，... 实施例3α4，其它为α5a，b，c，δac，δca ，α6a，b，c，δca，δbc，α7a，b，c，δca，δcb，δac，α8a，b，c，δca，δcb，δbc，α9a，b，c，δca，δac，δbc. 此外，分配给每个AAF的概率Ai， Di是概率的乘积（分别地，概率的补数）Ai中的参数（分别为， 在A中，而不是在 Ai）和概率（分别， Di中失败的概率的补数）（分别为，Ai中的论点在D中但不在Di中的失败）。例如，P（α1）=P（a）× P（b）×（1 − P（c））= 0。P（α3）= P（a）× P（b）× P（c）× P（δca）× P（δcb）×（1 − P（δac））×（1 −P（δbc））= 0。26. □在下文中，给定任何种类的prAAF F=（A，D，P）（因此，独立于P被编码的方式），我们表示sF。α→=α1，. ，α是由P分配非零性能的可能AAF，并且是F。P→=P（α1），. ，P（αm）的概率。对于实例，如果F被编码为形式的prAAF，则n个F。α→F。在编码F的元组（A，D，α→，P →）中，P →是α →和P→。 类似地，如果F是前一种，则nF. α→是所有可能的AAF定义在A和D上的条件，并且. P→是等式（1）中定义的pd f。值得注意的是，ind和ex可以被视为允许概率被具体化的极端和相反的方式。一方面，ind是紧凑的，因为它只需要为每个论点和失败指定概率，其数量一般情况下，nAD小于nS（注意nS是O（2nAD））。然而，ind假设每对参数和/或失败之间的独立性，因此当想要指定相关性时不能使用它。 另一方面，ex是完备的，因为它允许在每个可能的场景中直接指定概率，但它是冗长的，因为随着要考虑的场景数量的增加，越来越多的概率必须被指定。 在下文中，我们将介绍一个新的prAAF，称为gen，其中使用世界集描述符的范式对可能场景的pdf进行编码。这种范式在某种程度上介于ex和ind之间：它具有相同的表达性作为形式Ex（因为它允许对任何PDF进行编码，从而允许表达任何相关性），但是更紧凑，因为它的编码不需要具有非零概率的场景的显式枚举2.4. 概率环境中的推理：P-Extsem（S）和P-Accsem（a）当切换到概率设置时，决策问题Extsem（S）没有意义，因为许多不同的场景是可能的，并且一组参数在某些场景中可以是扩展，但在其他场景中则不是。 因此，检验一组论点S的“合理性”的问题的最自然的lemP-Extsem（S），用于评估S是扩展的概率，根据以下文献中的定义。定义1（P-Extsem（S）和P sem（S））。 [14，16]给出一个prAAF，一套 S 的论点，和语义semSEM，P-Extsem（S）是计算S是根据sem的扩展的概率Psem（ S）的问题，即：Psem（S）=α ∈ F。α→εext（α，sem，S）F. P（α）（2）实施例5. 考虑示例3，设置{a，b}（分别， {c}）是由P（α1）+P（α2）= 0给出的容许扩张。4. 类似地，Pad（{c}）= P（α2）+P（α3）+P（α4）= 0。9. 相反，考虑示例4，Pad（{a，b}）B. Fazzinga等人 /《人工智能》268（2019）1-2972ACCACCF∈ACCACC21=1122我2PH类=i≥0P。复杂度类©p是CUP的子类，也称为P ||NP，这是决策类2我我我表1不同形式的prAAF的Extsem（S）和P-Extsem（S）的复杂性（Extsem（S）的结果来自文献）。semExtsem（ S）P-Extsem（ S）Ind ex gen，bool，Ind-dmon，Ind-aPFP FP#P-cFP稳定P FP FP#P-cFP完成P FP#P-cFP FP#P-cFP#P-c接地PFP#P-cFPFP#P-cFP#P-c半稳定coNP-cFP#P-cFP||NP-cFP#P-cFP#P-c首选coNP-cFP#P-cFP||NP-cFP#P-cFP#P-c理想集coNP-cFP#P-cFP||NP-cFP#P-cFP#P-cidealin ©p，coNP-hFP#P-cFP||NP-cFP#P-cFP#P-c等于P（α1）+P（α4）+P（α5）+P（α6）+P（α7）+P（α8）+P（α9）= 0。676，并且Pad（{c}）等于P（α2）+P（α3）+P（α4）+P（α5）+P（α7）+P（α8）= 0。829. □类似地，当从确定性环境转移到概率性环境时，接受问题Accsem（a）就变成了通过考虑所有备选方案来评估a下面我们报告从文献中获得的P-Accsem（a）和Psem（ a）的定义定义2（P-Accsem（a）和P sem（a））。 [17]给定一个prAAF，一个参数a和一个语义sem SEM，P-Accsem（a）是计算概率Psem（a）的问题，其中a属于根据sem的至少一个扩展，即：Psem（a）=.F. P（α）（3）α ∈ F。α→β-S|（ext（α，sem，S）<$a∈S）在下文中，给定prAAFf的形式，我们将相同的问题P-Extsem（S）表示为P-Extsem（S）和P-Accsem（a）。f f和P-Accsem（a），分别限制于输入prAAF具有形式f的情况2.5. 复杂度类与其他提供关于决策问题Extsem（S）和Accsem（a）的复杂性结果的论文相比，这里我们还必须求助于函数复杂性类（如[16]中所做的），这更适合于表征P-Extsem（S）和P-Accsem（a）的复杂性，因为它们本质上是研究问题。因此，我们在这里简要回顾了本文其余部分中使用的决策复杂性和函数复杂性类P（resp. NP）是一类决策问题，可以解决的确定性（或）。非确定性）图灵机在多项式时间w.r.t.输入问题的大小。coNP是其补在NP中的决策问题类。证明了P<$NP，P<$coNP，NP/=coNP.多项式层次结构如下P P P类序列：设P=P=P=P，对所有i≥0，P=P，P=NP，CUP=coNP，其中 XY表示0 0 0i+1i+1i+1可以通过类X中的算法调用类Y中的预言来解决的问题的类。第一，在第二个层次（i=2）中，我们有P=P，P=NP，P=coNP，和PNPcoN PNP。 各级 i>0时，这三个类通过对于 P， NP和coNP. 此外，每个级别的每个班级包括以前级别的所有班级（累积）多项式层次结构是可以通过多项式时间图灵机向NPoracle并行询问来解决的问题（这里，并行意味着可以以非自适应的方式进行oracle的调用，在这个意义上，在任何调用时询问的内容不依赖于任何其他调用的结果）。结果表明，P||NP与P NP[log n]一致（在这种情况下，Oracle机器最多可 以 请 求 O（log n）个自适应查询）。FP是一类可以由确定性图灵机在多项式时间（w.r.t.）内解决的函数问题。输入问题的大小）。在本文中，我们特别处理类FP#P和FP||NP. FP#P是可由多项式时间图灵机和#Poracle计算的函数类。#P是函数f的复杂度类，使得f计数非确定性多项式时间图灵机的接受路径的数量[21]。类似地，FP||NP是可由多项式时间图灵机计算的函数类，可以访问NP oracle，其调用是非自适应的（如上所述，这相当于说oracle调用并行发生）。我们将利用以下关于不同函数复杂性类之间关系的结果：（i）对于每个复杂性类#C∈#PH，它保持FP#P=FP#C，因为#PH<$FP#P[1]在多项式时间1-Turing re下，8B. Fazzinga等人 /《人工智能》268（2019）1-29p||NP⊆ex2exex联系我们联系我们=∈ []⊆∈表2不同形式的prAAF的Accsem（a）和P-Accsem（a）的复杂性（Extsem（S）的结果来自文献）。semAccsem（ a）P-Accsem（ a）Ind ex gen，bool，Ind-d mon，Ind-a容许NP-cFP||NP-c稳定NP-cFP||NP-c完全NP-cFP||NP-c接地PFP#P-cFPFP#P-cFP中的半稳定的α2-c||2002年，FP||NP-hpp优选NP-cFP||NP-cp，coNP-hFP中的理想集||NP-c理想2©2，coNP-hFP-c导管 [22]， FPFP#P[1]FP#P;（ii）函数是 FP#P-hard当且仅当它是#P-hard，2 从而证明一个问题FP#P-hard它可以将一个#P-hard问题简化为它。3. P-EXTsem（S）和P-ACCsem（a）前前我们在这里提供我们的论文的第一个贡献。给定P-Extsem（S）和P-Accsem（a）在形式为Ind的prAAF上的复杂性已经在[16，17]中被表征，我们在这里通过表征它们在形式为ex的prAAF上的复杂性来完成这些基本问题的复杂性的图片。特别地，我们将证明P-Extsem（S）对于任何语义sem是多项式时间可解的，其确定性对应物Extsem（S）是多项式时间可判定的，并且它是FP||对于SEM中的所有其他语义，NP -完全（其确定性对应物Extsem（S）是NP-完全或©p-完全-参见表1）。定理1. P-Extsem（S）在FP中，对于sem ∈ {ad，st，gr，co}。证据 计算等式（2）可以在多项式时间内完成的事实直接从以下事实得出I.对于每个sem_ad、st、gr、co，判定S是否是确定性AAF中的扩展（即，求解Extsem（S））在PTIME中;ii.在输入中，必须对其执行该检查的可能AAF的数量是线性的（我们记得，ex的大小与可能的AAF的数量成比例）。□定理2. P-Extsem（S）为FP||对于sem∈ {pr，ids，ide，sst}是NP完全的.证据F P成员||NP. 对于语义sst、pr和ids（其中Extsem（S）是coNP完全的），FP||NP从以下事实得 出：P-Extsem（S）可以通过对NP 预言机执行尽可能多的并行调用（每个求解Extsem（S）ex在具有非零概率的可能AAF上）作为编码的在prAAF。对于语义ide，FP的成员资格||NP仍然成立，因为具有对预言机的并行调用的多项式时间图灵机可以容 易 地转换为具 有 并 行 调 用 的多项式时间图灵机。2到NPp=P||NP）。预言（这是因为）F P硬度||NP. 我们将显示从FP减少||NP-困难问题sup（φ），即计算3CNF布尔公式φ（x1，...，x n）。 我们记得上确界sup（φ）是赋值，其中，对于每个i 1. n，则变量x i被赋值为真当且仅当存在φ的满意赋值，其中x i为真.为了便于演示，我们首先展示了semid，ide的约简，然后我们讨论了首选和半稳定语义的情况。设φ=C1<$C2<$··<$Ck是集合X= {x1，...，xn}的变量。我们建立n个公式φ1，...，其中每个φi具有形式φi=C i，1<$C i，2<$··<$C i，ki，并且通过指定x i=true从φ获得。这里，ki≤k，因为包含xi的φ的子句求值为真，因此从φi中移除。此外，在建设φi，任何出现 第十章 删除，因此任何条款 C i，j 的 φi 可以具有 |= 2或| = 2 or|= 3个文字（w.l.o.g.|= 3 literals (w.l.o.g. 我们假设φ的每个原始子句包含不同变量的文字我们表示[2]如果一个问题是F P#P-hard，那么它显然是#P反之亦然，可以证明，任何问题A∈F P#P都可以在多项式时间1-图灵约简推理下约简为#P-困难问题B， F P#P意味着存在多项式时间算法MA，该算法仅使用对#PoracleC的一次调用来求解A（如F P#PF P#P[1]）。此外，由于B是#P-困难的，因此存在多项式时间算法MC求解预言C。（在MA中使用）只使用一次对Boracle的调用。因此，通过组合MA和MC，我们得到了一个多项式时间算法，该算法通过使用对Boracle的一次调用来求解A，这意味着A可以在多项式时间1-图灵约简下约简为BB. Fazzinga等人 /《人工智能》268（2019）1-299¬∈·=···F{}exex关于我们（）{}联系我们<$∈ ==联系我们{}（）=∈{}Fi、j·= {|【详细】我i、j 中发生i、ji、ji、ji、j12Fig. 1. AAF（A1，D1）=β（φ1）的图形表示，其中φ1=（x2<$x3）<$（<$x2<$x3）由3-CNF公式φ=（<$x1<$x2<$x3）<$（<$x1<$$>x2<$x3）<$（x1<$x4<$x5）通过指定x1=true。X 的 子 集 包 含 仍 然 出 现 在 φi 中 的 变 量 作 为 X （ φi ） ， X （ φi ） 的 基 数 作 为 ni 。 例 如 ， 从 φ= （ <$x1<$x2<$x3 ）<$（<$x1<$$>x2<$x3）<$（x1<$x4<$x5）开始，其中X={x1，x2，x3，x4，x5}且k=3，在指定x1=真之后，我们得到φ1=（x2<$x3）<$（<$x2<$x3），其中X（φ1）={x2，x3}且k1=2。然后，我们定义如下组成部分的形式的prAAFFφ=（A，D，α→，P→）：一A0A n，其中A0由一个参数s组成，而每一个其他A i包含（i）一个参数Ci，j，对应于出现在φi中的每个子句Ci，j;（ii）两个参数xl和xl，对应于每个变量xl X（φi）;（iii）两个参数i，φi;（iv）参数s。• D=D0<$··<$Dn，其中 D0 只包含失败δ0=（s，s），而彼此 Di （一）两次失败天心座δ =（i，i）和δφi =（φi，φi）;（ii）两个失败δi=（s，φi）和δi=（φi，s）;（iii）对于φi的每个子句Ci，j，一个失败δi，j=（C） ， φ）;（iv）对于每个条款C1 2luC（其中u∈ [1..|C|]), a defeat δu=（lu，C），在哪里l u是形式为 x l或<$x l的自变量，其中x l∈X（φi）;（v）两个 失败δxl =（x l，<$x l）和δxl =（<$xl，xl），（vi）对于每个变量xl∈X（φi），有两个定理δi=（i，xl）和δi=（i，<$xl）.l和1• α→=α0，α1，. ，αn，其中reαi=（Ai，Di），对于eachi∈[1. . n];l，2• P→=P0，P1，. ，Pn，其中P0=1/2n，且对于每个ci∈[1. . n]，Pi=2i−1/2n.我们考虑从φ1，...，φn到AAF（A1，D1）.，（An，Dn）使得对于每个φi，β（φi）=（Ai，Di）. AAF（A1，D1）=β（φ1）的图形表示见图1，其中φ1=（x2<$x3）<$（<$x2<$x3）1.很容易看出，{s}不是AAF（A i，D i）中的理想集扩张（因此，它不是理想扩张），当且仅当存 在 对x1，...，xi−1，x i+1，.，x n使得φi的值为真。事实上，如果这样的t存在，就有可能找到一个无冲突的集合L，它有n i个参数，可以保护φi不受来自C